ZOJ 2955 Interesting Dart Game：鴿巢原理優化完全背包

題目建模

給定 n 種飛鏢得分 w[i]，每種可無限使用，求達到總分 m 所需最少飛鏢數。這是一個「代價為 1 的完全背包」問題，但 m 可高達 10^9，直接 DP 會超時。

鴿巢原理優化核心結論

設最大得分為 W = max(w[i])。對於任意目標分數 m >= W^2，最優解中得分 W 的飛鏢數量至少佔多數。具體可證明：

• 先用 DP 解出 [0, W^2) 範圍內所有分數的最少飛鏢數 dp[x]。
• 對於 m >= W^2，令 k = (m - W^2) / W + 1，則答案 = k + dp[m - k*W]。

這將問題規模從 O(m) 降為 O(W^2)，其中 W <= 1000（題目約束），完全可行。

完整算法流程

1. 讀入得分數組，排序，取最大值 W = w[n]。
2. 計算 maxn = W * W。
3. 初始化 dp[0]=0, dp[others]=-1。
4. 完全背包 DP 填充 dp[0...maxn-1]。
5. 若 m < maxn 直接輸出 dp[m]；否則按上述公式計算。

核心代碼

#include 
using namespace std;
const int MAXW = 1000;
int dp[MAXW * MAXW + 5];
int w[105];

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        int n, m; scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; ++i) scanf("%d", &w[i]);
        sort(w + 1, w + n + 1);
        int W = w[n];
        int maxn = W * W;
        memset(dp, -1, sizeof(dp));
        dp[0] = 0;
        for (int i = 1; i <= n; ++i)
            for (int j = w[i]; j < maxn; ++j)
                if (dp[j - w[i]] != -1 &&
                    (dp[j] == -1 || dp[j - w[i]] + 1 < dp[j]))
                    dp[j] = dp[j - w[i]] + 1;
        if (m < maxn) {
            printf("%d\n", dp[m]);
        } else {
            int k = (m - maxn) / W + 1;
            int rem = m - k * W;
            if (dp[rem] == -1) puts("-1");
            else printf("%d\n", k + dp[rem]);
        }
    }
    return 0;
}

複雜度分析

• 時間：O(n * W^2)，W <= 1000 時約 10^7 操作，極快。
• 空間：O(W^2) ≈ 10^6 整數，約 4 MB。

此題是「數學洞察優化 DP」的教科書級範例，鴿巢原理將看似不可行的大數據範圍化歸為小規模預計算。