dp - Google Code jam Qualification Round 2015 --- Problem B. Infinite House of PancakesProblem B. Infinite House of Pancakes Problem's Link: https://code.google.com/codejam/contest/6224486/dashboard#s=p1

Mean: 

有無限多個盤子，其中有n個盤子裡面放有餅，每分鐘你可以選擇兩種操作中的一種：

1.n個盤子裡面的餅同時減少1；

2.選擇一個盤子裡面的餅，分到其他盤子裡面去；

目标是讓盤子裡的餅在最少的分鐘數内吃完，問最少的分鐘數。

analyse:

可以分析出，先分再吃不會比先吃再分差，是以我們選擇先分再吃。

首先用dp預處理，dp[i][j]表示：初始時為i個餅的盤子經過分以後最大值為j需要多少步。

然後我們就可以暴力+貪心了，枚舉吃的次數(1~MAX)，對于每一個吃的次數，我們需要把每個餅都分到小于或等于這個次數。詳見代碼。

Time complexity: 小于 O(n^3)

Source code: 

View Code