動態規劃經典題：HDU 1074 Doing Homework 狀態壓縮 DP 完整解析

完整 C++ 代碼

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAXN = 15;
const int MAXS = 1 << MAXN;

int dp[MAXS], tm[MAXS], pre[MAXS];
int D[MAXN], C[MAXN];
char name[MAXN][110];

void print_path(int mask) {
    if (!mask) return;
    print_path(mask ^ (1 << pre[mask]));
    puts(name[pre[mask]]);
}

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        int N; scanf("%d", &N);
        for (int i = 0; i < N; i++)
            scanf("%s %d %d", name[i], &D[i], &C[i]);
        int ALL = 1 << N;
        fill(dp, dp + ALL, INF);
        fill(tm, tm + ALL, 0);
        dp[0] = 0;
        for (int mask = 1; mask < ALL; mask++) {
            for (int i = 0; i < N; i++) if (mask & (1 << i)) {
                int prev = mask ^ (1 << i);
                int cur_t = tm[prev] + C[i];
                int pen = max(0, cur_t - D[i]);
                if (dp[prev] + pen < dp[mask]) {
                    dp[mask] = dp[prev] + pen;
                    tm[mask] = cur_t;
                    pre[mask] = i;
                }
            }
        }
        printf("%d\n", dp[ALL - 1]);
        print_path(ALL - 1);
    }
    return 0;
}

關鍵細節

1. 字典序最小：題目要求同分時輸出字典序最小順序。因輸入已按名稱排序，枚舉 i 從 0 到 N-1，pre 記錄最後做的作業，回溯時遞迴先印前驅再印當前，自然產生字典序最小解
2. 時間複雜度：O(N·2^N) ≈ 15·32768 ≈ 50萬次操作，極快
3. 空間複雜度：O(2^N) 三個陣列，約 400KB

狀態壓縮 DP 通用模式

for mask in 0 .. (1<
HDU 1074 是狀態壓縮 DP 入門最佳範例，掌握其「集合狀態、枚舉最後一步、前驅回溯」三步法，即可解決大多數 N≤20 的排列/子集優化問題。