鸽巢原理人人都有耳闻，十只鸽子飞进九个巢，必定有一个巢里不少于两只鸽子。但是真正要用的时候，它却总是来得悄无声息。就像电影《The Blues Brothers》里面的牧师说的：“The day of the Lord cometh is as a thief in the night”。

    ZJU 2955 乍一看是再典型不过的动态规划问题：给出 N （N < 100）个 (0, 100) 范围内的整数，问最少从中取出几个数，可以使它们相加正好等于一个指定的整数 S（每个数可以取的次数不限）。

    有一点 ACM 经验的同学肯定一看就知道这是一个 O(S × N) 的动态规划。可是问题是，这道题目里 S 的范围是 [1, 10⁹]。要解决这个问题，首先需要用鸽巢原理来证明下面这个定理：

    设可选的 N 个数从小到大依次为 a₍₁₎、 a₍₂₎ … a_(N)，则在最优的取法中，小于 a_(N) 的数不会多于 a_(N) 个。

    可以用反证法来证明。假设在最优的取法中，有 M 个小于 a_(N) 的数（M > a_(N)）。让我们把这 M 个数随便排列起来，记为 b₁、 b₂ … b_M。再设 S_i = b₁ + b₂ … + b_i （1 ≤ i ≤ M）。

    由于一个数除以 a_(N) 的余数只有 a_(N) 种可能性，即 0 到 a_(N) - 1，又因为 M > a_(N)，所以一定存在一对 S_i 与 S_j （1 ≤ i < j ≤ M）满足 S_i mod a_(N) = S_j mod a_(N)。也就是说，S_j - S_i 是 a_(N) 的倍数，也就是说，b_{i + 1} + b_{i +2} … + b_j 是 a_(N) 的倍数。然而，根据之前的假设，b₁ … b_M 都是小于 a_(N) 的。因此，如果把 b_{i + 1} + b_{i +2} … + b_j 这一块全部用 a_(N) 来填补，则可以用更少的数。这样一来，假设中的取法就不是最优取法了。反证完毕。□

    有了上面的定理，问题就好解决了。不多于 a_(N) 个小于 a_(N) 的数，加起来的和不会超过 a_(N)² ，即不超过 10,000。S 在这个范围内的最优解是可以用动态规划全部求出来的，花 O(10⁶) 的时间。如果 S > a_(N)² 的话，只要枚举所有的 S’ ∈ [1, a_(N)²]，然后 S - S’ 的部份全部用 a_(N) 来填充，即可找到最优解。