HDU 4939 Stupid Tower Defense：DP 優化塔防傷害輸出

題目大意

長度為 n 的直線地圖，每格放一座塔。敵人每格基礎耗時 t 秒。三種塔：

• 紅塔：敵人通過時，每秒造成 x 傷害。
• 綠塔：敵人通過後，每秒額外造成 y 傷害（疊加）。
• 藍塔：敵人通過後，每格移動額外耗時 z 秒（減速，疊加）。

若已通過 g 綠塔、b 藍塔，則後續每秒傷害增加 g·y，每格耗時變為 t + b·z。求塔的排列順序使總傷害最大化。

關鍵貪心觀察

紅塔一定放在最後面。因為紅塔只對「通過它那一刻」的傷害有貢獻，不影響後續。將紅塔前移只會減少其前方的綠/藍塔數量，降低紅塔生效時的傷害倍率與時間。故最優排列為：[綠/藍混排] + [紅塔群]。

DP 狀態定義

設前綴中不含紅塔，僅考慮綠塔與藍塔的排列。
dp[i][j]：前 i 格塔中，放了 j 個綠塔（其餘 i-j 為藍塔）的最大累積傷害貢獻（不含最終紅塔段）。

轉移方程

• 第 i 格放藍塔（j 不變）：
  dp[i][j] = max(dp[i][j], dp[i-1][j] + y * j * (t + (i-j-1)*z))
  解析：當前已有 j 綠塔、i-j-1 藍塔，新藍塔通過時傷害率 y·j，耗時 t + (i-j-1)z。
• 第 i 格放綠塔（j-1 → j）：
  dp[i][j] = max(dp[i][j], dp[i-1][j-1] + y * (j-1) * (t + (i-j)*z))
  解析：放綠塔前有 j-1 綠塔、i-j 藍塔，新綠塔通過時傷害率 y·(j-1)，耗時 t + (i-j)z。

最終答案計算

枚舉紅塔數 red = 0..n，綠塔數 green = 0..n-red，藍塔數 blue = n - red - green。
總傷害 = dp[n-red][green] + (t + blue*z) * red * (x + green*y)
解析：紅塔段耗時 t + blue*z，每秒傷害 x + green*y，共 red 格紅塔。

完整代碼

複雜度分析

DP 狀態 O(n²)，n ≤ 1500 → 約 2.25e6 狀態，轉移 O(1)，總時間 ~0.1s。
空間 O(n²) ≈ 18 MB（long long），可滾動數組優化至 O(n)。


易錯點提醒

紅塔必須放最後，否則 DP 狀態定義不成立。
傷害計算公式仔細核對：綠塔疊加的是「每秒傷害」，藍塔疊加的是「每格耗時」。
初始值 ans = n*x*t 對應全紅塔情況（無綠/藍塔）。
枚舉紅塔數時，綠塔數 j 即為 green，藍塔數 i-j 即為 blue。