USACO 2014 December Contest, Gold Problem 1. Guard Mark

原題下載

USACO2014-DEC-G1

答案
(Analysis by Bill Cooperman)

An initial observation for many experienced contestants is that there can be no more than 20 cows. Immediately this suggests some solution that is exponential in n, possibly examining all subsets of cows. However, the order in which the cows are stacked is important as well. Specifically, it can quickly be shown that the optimal arrangement of cows might not be sorted in order of strength or weight (this is left as an exercise to the reader). Luckily, the problem of finding an optimal arrangement of some subset of the cows can be deconstructed into several smaller sub-problems of the same type, so it is possible to construct a dynamic programming solution.

Let f(C) be the maximum possible strength factor for a stack of cows consisting of exactly the subset C of all the cows. Then the solution to our problem is just the maximum f(C) for all C where the sum of all the heights of cows in C is at least H. Now, we just need to calculate f(C). If we let f(?)=∞ (analagous to the ground being able to support all the cows' weights), then we have the recurrence

Intuitively, we are trying to place each cow c∈C on the bottom of the stack, and then placing the remaining set C?c of cows above c. The straightforward implementation of this idea runs in O(n2ⁿ) time (assuming the sum of weights of cows in a subset is pre-computed), which is fast enough to get full points.

以上就是關于【USACO 2014 December Contest, Gold Problem 1. Guard Mark】的解答，如需了解學校/賽事/課程動態(tài)，可至翰林教育官網獲取更多信息。

往期文章閱讀推薦：

NOAI、UKOAI、USAAIO三大AI奧賽新賽季全面啟動：留學申請的“核武器”來了！

耗時一年備考 USACO 卻毫無收獲？一文教你找準最佳備考起步時間！