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】的解答，如需了解学校/赛事/课程动态，可至翰林教育官网获取更多信息。

往期文章阅读推荐：

USACO计算机奥赛如何认证成绩？2026赛季黄金铂金组“定时开赛”规则详解！

USACO计算机奥赛考试语言是什么？C++、Python、Java选哪个效率最高？