UVA 12563 Jin Ge Jin Qu hao：01 背包變體求最大歌曲數

問題大意

有 N 首歌，每首長度 t_i。總時間限制 T，但最後必須預留 678 秒（固定尾聲）。求在不超時前提下，最多能放多少首歌；若歌曲數相同，總時長越長越優。輸出最大歌曲數與對應總時長。

DP 狀態設計

經典 01 背包：dp[j] 表示總時長恰為 j 時的最大歌曲數。初始 dp[0]=0，其餘 -1 表示不可達。

狀態轉移

對每首歌（含尾聲），逆序更新：

for j = min(T-1, 10000) down to 0:
    if dp[j] != -1:
        dp[j + t_i] = max(dp[j + t_i], dp[j] + 1)

注意：總時長上限取 10000（題目隱含），且不超過 T-1（預留 1 秒緩衝）。

答案提取

掃描 dp 數組，優先最大化歌曲數，次之最大化時長：

for i = 11000 down to 0:
    if ans_songs < dp[i]:
        ans_songs = dp[i], ans_time = i

完整代碼

#include <bits/stdc++.h>
using namespace std;
const int MAXT = 11005;
int T, n, t, song[55], dp[MAXT];

int main() {
    int cas = 0; scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &n, &t);
        for (int i = 0; i < n; ++i) scanf("%d", &song[i]);
        song[n++] = 678; // 固定尾聲
        fill(dp, dp + MAXT, -1);
        dp[0] = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = min(t-1, 10000); j >= 0; --j)
                if (dp[j] != -1)
                    dp[j + song[i]] = max(dp[j + song[i]], dp[j] + 1);
        }
        int ans1 = 0, ans2 = 0;
        for (int i = MAXT-1; i >= 0; --i)
            if (ans1 < dp[i]) { ans1 = dp[i]; ans2 = i; }
        printf("Case %d: %d %d\n", ++cas, ans1, ans2);
    }
    return 0;
}

關鍵細節

1. 尾聲 678 作為一首必選「歌」加入數組
2. 背包容量上限取 min(t-1, 10000)，雙重保險
3. 逆序更新保證 01 背包每物品只用一次
4. 答案從大到小掃描，天然滿足「時長最大」次優條件

此題是 01 背包「最大件數、次優最大重量」的標準變體，代碼簡潔高效。