ZOJ 3623 Battle Ships：動態規劃求最短勝利時間

ZOJ 3623 Battle Ships

遊戲場景：敵方防禦塔生命值 L，工廠可生產 N 種戰艦。第 i 種戰艦生產需 t_i 秒，生產完成後每秒造成 l_i 傷害。每次只能生產一種（可重複生產同種）。求摧毀塔的最短時間。

問題建模

• 狀態：時間 j 內造成的最大傷害 `dp[j]`。
• 決策：在時間 j 選擇生產第 i 種戰艦，花費 t_i 時間，剩餘 j 時間每秒傷害 l_i，總傷害 `dp[j] + j * l_i`。
• 轉移：`dp[j + t_i] = max(dp[j + t_i], dp[j] + j * l_i)`。
• 目標：找最小 T 使 `dp[T] ≥ L`。

動態規劃詳解

這是一種「生產即投資」的背包變體：花費時間 t_i 獲得持續收益 l_i。類似完全背包但收益隨剩餘時間線性增長。

代碼實現（C++）

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

const int MAXL = 330;
const int MAXT = 2000; // 足夠大的時間上限

int dp[MAXT+1];
int t[35], l[35];

int main() {
    int N, L;
    while(scanf("%d%d", &N, &L) == 2) {
        for(int i = 1; i <= N; i++) scanf("%d%d", &t[i], &l[i]);
        memset(dp, 0, sizeof(dp));
        int ans = -1;
        for(int T = 1; T <= MAXT; T++) {
            for(int i = 1; i <= N; i++) {
                if(T >= t[i]) 
                    dp[T] = max(dp[T], dp[T - t[i]] + (T - t[i]) * l[i]);
            }
            if(dp[T] >= L) { ans = T; break; }
        }
        printf("%d\n", ans);
    }
    return 0;
}

關鍵點

• 時間上限估算：最差情況每秒傷害 1，L=330，需 330 秒；加上生產時間，設 2000 足夠安全。
• 狀態轉移順序：T 從小到大，內層枚舉戰艦，類似完全背包。
• `dp[T]` 表示恰好用 T 秒能造成的最大傷害（含生產時間）。

樣例驗證

輸入:
1 1
1 1
2 10
1 1
2 5
3 100
1 10
3 20
10 100

輸出:
2
4
5

總結

本題將「生產-收益」建模為時間維度上的 DP，核心是識別出 `dp[T]` 的物理含義並正確推導轉移方程。屬於背包問題的變體應用。