ZOJ 3623 Battle Ships：完全背包變體求最短摧毀時間

問題重述

有 N 種戰艦（N ≤ 30），防禦塔血量 L（L ≤ 330）。第 i 種戰艦：

• 生產時間 t_i（1~20 秒）
• 每秒傷害 l_i（1~330）

工廠同一時間只能生產一種戰艦，可重複生產同種。求將塔血量降至 ≤ 0 的最短時間。

關鍵建模：時間維度的完全背包

定義 dp[t] = 前 t 秒內能造成的最大總傷害。狀態轉移：

對於每種戰艦 i，若在第 j 秒開始生產，於 j+t_i 秒完成，之後每秒產生 l_i 傷害。但更直觀的建模是：

• 生產一艘戰艦 i 消耗 t_i 時間
• 完成後「獲得」一個每秒產生 l_i 傷害的持久輸出源
• 總傷害 = Σ (存活時間 × l_i)

經過推導，等價於：

dp[j + t[i]] = max(dp[j + t[i]], dp[j] + j * l[i])

其中 j 代表「開始生產的時刻」，j * l[i] 代表這艘艦從生產完到終點的累積傷害貢獻（假設終點固定）。實際上這是將問題轉化為：在時間軸上選擇生產時刻，最大化加權和。

完整解法代碼

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAXT = 40000;  // 足夠大的時間上界
int dp[MAXT];
int t[35], l[35];

int main() {
    int n, L;
    while (scanf("%d%d", &n, &L) == 2) {
        for (int i = 0; i < n; ++i) scanf("%d%d", &t[i], &l[i]);
        memset(dp, 0, sizeof(dp));
        
        // 完全背包：外層遍歷物品，內層正序遍歷時間
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j + t[i] < MAXT; ++j) {
                dp[j + t[i]] = max(dp[j + t[i]], dp[j] + j * l[i]);
            }
        }
        
        // 找最早達標時刻
        for (int ans = 0; ans < MAXT; ++ans) {
            if (dp[ans] >= L) {
                printf("%d\n", ans);
                break;
            }
        }
    }
    return 0;
}

狀態轉移圖解

時間軸：0 ---- j ---- j+t_i ---- T
             ↑生產開始  ↑生產完成
傷害貢獻：          (T - (j+t_i)) * l_i
代碼中近似用 j * l_i 反映「越早生產貢獻越大」

複雜度與優化

• 時間：O(N × MAXT) ≈ 30 × 40000 = 1.2e6，極快
• 空間：O(MAXT)
• MAXT 可設為 max_t * max_L / min_l + max_t 估算上界，40000 足夠安全

核心洞察

將「持續輸出」轉化為「時間加權和」是本題精髓。類似思想常見於：

• 投資理財：資金佔用時間產生收益
• 任務調度：提前完成任務獲得額外獎勵
• 資源分配：早期投入產生複利效應