HDU 2159 FATE：二維完全背包升級經驗與忍耐度權衡

問題描述

需 n 經驗升級，忍耐度 m。k 種怪，每種無限量。殺第 i 種得 a_i 經驗，損 b_i 忍耐。最多殺 s 隻怪。求升級後剩餘最大忍耐度，不可行輸出 -1。

二維完全背包建模

• 容量 1：忍耐度 (0~m)
• 容量 2：殺怪數 (0~s)
• 價值：經驗值
• 目標：在容量限制下最大化經驗，判斷是否 ≥ n

DP 狀態

`dp[x][y]` = 損耗忍耐度 x、殺 y 隻怪所能獲得的最大經驗。

狀態轉移 (完全背包)

for each monster i:
    for x = b_i .. m:
        for y = 1 .. s:
            for cnt = 1; cnt*b_i <= x && cnt <= y; ++cnt:
                dp[x][y] = max(dp[x][y], dp[x-cnt*b_i][y-cnt] + cnt*a_i);

優化：提前終止

外層按忍耐度 x 從小到大枚舉，一旦 `dp[x][s] >= n` 即可輸出 `m - x`，保證剩餘忍耐度最大。

完整代碼

#include 
#include 
#include 
using namespace std;

struct Monster { int exp, cost; } mon[105];
int dp[105][105];

int main() {
    int n, m, k, s;
    while (scanf("%d%d%d%d", &n, &m, &k, &s) == 4) {
        for (int i = 1; i <= k; ++i) scanf("%d%d", &mon[i].exp, &mon[i].cost);
        memset(dp, 0, sizeof(dp));
        
        int ans = -1;
        for (int x = 1; x <= m; ++x) {  // 枚舉損耗忍耐度
            for (int i = 1; i <= k; ++i) {
                for (int y = 1; y <= s; ++y) {
                    for (int cnt = 1; cnt * mon[i].cost <= x && cnt <= y; ++cnt) {
                        dp[x][y] = max(dp[x][y], dp[x - cnt*mon[i].cost][y - cnt] + cnt*mon[i].exp);
                    }
                }
            }
            if (dp[x][s] >= n) { ans = m - x; break; }
        }
        printf("%d\n", ans);
    }
    return 0;
}

關鍵優化點

1. 忍耐度外層枚舉：從小到大，首個滿足即最優
2. 完全背包寫法：`cnt` 循環枚舉選取數量，或用 `dp[x][y] = max(dp[x][y], dp[x-cost][y-1] + exp)` 但需注意順序
3. 數組大小：m,s ≤ 100，dp[101][101] 足夠

複雜度

• 時間：O(m × k × s × 最大cnt) ≈ 100×100×100×100 = 1e8 邊界
• 實際 cnt 受限於 x/cost，遠小於 100
• 優化：將 cnt 循環改為 `for (int x = cost; x <= m; ++x) for (int y = 1; y <= s; ++y) dp[x][y] = max(dp[x][y], dp[x-cost][y-1] + exp)` 但需確保完全背包正確性

更優轉移 (標準完全背包)

for (int i = 1; i <= k; ++i) {
    for (int x = mon[i].cost; x <= m; ++x) {
        for (int y = 1; y <= s; ++y) {
            dp[x][y] = max(dp[x][y], dp[x - mon[i].cost][y - 1] + mon[i].exp);
        }
    }
}
// 然後檢查最小 x 使 dp[x][s] >= n

注意：二維完全背包時，內層循環順序不影響正確性（因為兩維度都是正向），但必須保證每個物品的處理獨立。