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.