ZOJ 3623 Battle Ships：完全背包動態規劃最短擊沉時間

ZOJ 3623 經典動態規劃問題：工廠生產戰艦攻擊防禦塔，每種戰艦有生產時間 tᵢ 和每秒傷害 lᵢ，求擊沉塔 (血量 L) 的最短時間。

問題建模

• N 種戰艦 (N ≤ 30)，塔血量 L (L ≤ 330)
• 生產第 i 種戰艦需 tᵢ 秒，生產完成後每秒造成 lᵢ 傷害
• 同一時間只能生產一種，可重複生產同種
• 目標：最小化總時間 T，使累積傷害 ≥ L

關鍵洞察：時間作為背包容量

定義 dp[j] = 第 j 秒結束時能造成的最大總傷害。

若在第 j - tᵢ 秒開始生產第 i 種戰艦，則在 j 秒時：

• 前 j - tᵢ 秒最大傷害：dp[j - tᵢ]
• 新戰艦從 j - tᵢ + 1 到 j 秒工作：tᵢ 秒 × lᵢ 傷害/秒
• 但實際生產完成需 tᵢ 秒，故工作時間為 j - tᵢ 秒

狀態轉移方程 (完全背包)

dp[j] = max(dp[j], dp[j - tᵢ] + (j - tᵢ) × lᵢ)

C 實作代碼

#include <stdio.h>
#include <string.h>

#define MAX_T 500  // 足夠大的時間上限

int dp[MAX_T];
int t[31], l[31];

int max(int a, int b) { return a > b ? a : b; }

int main() {
    int n, L;
    while (scanf("%d %d", &n, &L) != EOF) {
        for (int i = 1; i <= n; ++i) {
            scanf("%d %d", &t[i], &l[i]);
        }
        
        memset(dp, 0, sizeof(dp));
        
        // 完全背包：外層遍歷物品，內層遍歷容量 (正序)
        for (int i = 1; i <= n; ++i) {
            for (int j = t[i]; j < MAX_T; ++j) {
                dp[j] = max(dp[j], dp[j - t[i]] + (j - t[i]) * l[i]);
            }
        }
        
        // 找最小時間
        for (int j = 1; j < MAX_T; ++j) {
            if (dp[j] >= L) {
                printf("%d\n", j);
                break;
            }
        }
    }
    return 0;
}

範例驗證

複雜度分析

其中 T_max ≈ 500 為經驗上限 (L ≤ 330, lᵢ ≥ 1 → 最多 330 秒 + 生產時間)。

核心技巧總結

1. 反向思維：將「最小時間」轉化為「給定時間的最大傷害」
2. 時間即容量：離散秒數作為背包容量
3. 完全背包正序遍歷：允許重複生產同種戰艦
4. 傷害計算細節：(j - tᵢ) 為實際工作秒數，非 j