Google Code Jam 2017 Round1C

Problem A. Ample Syrup

The exposed area of the cake is (the base area of the largest pancake) + (the sum of the choosen K pancakes’ side area). If we have fixed the largest pancake, the answer can be calculated using dp. So we just enumerate the largest pancake.
Let dp[i][j] denote that the i’th pancake is choosen and there are j pancakes choosen among the first i pancakes.
Then dp[i][j] = max(dp[k][j-1]) + (S_i), of which S_i represents the side area of the i’th pancake.
The complexity is O(n^3), not a very good solution.

Problem B. Parenting Partnering

So many DPs in GCJ.
Let dp[i][j][k] represent among the first i minites, Cameron(player A) has already worked for j minutes and the people who was working at the i’th minute is k(k=1|2).
The equation is easy to derive.
Note that if the two peoples worked at the first and last minute are different(This can be simply determined by the parity of the dp value), we should add 1 to the answer.

Problem C. Core Training

I just solve the first(K=N) condition, yet I can’t prove its correctness.

发表评论