HDU 1074 Doing Homework：狀態壓縮 DP 最小化扣分

題目大意

Ignatius 有 N 門作業（N ≤ 15），每門有截止天數 D 和所需天數 C。逾期一天扣 1 分。安排做作業順序，使總扣分最小。若多種順序扣分相同，輸出字典序最小的順序（題目保證科目名已按字典序排列）。

狀態壓縮 DP

用二進制掩碼 mask 表示已完成的作業集合。dp[mask] 存儲：完成這組作業的最小扣分、總耗時、最後做的作業索引、前驅狀態。

狀態轉移：枚舉 mask 中的每一門作業 i 作為最後完成的，前驅狀態 pre = mask ^ (1<<i)。完成 i 的結束時間 = dp[pre].time + C[i]，扣分 = max(0, 結束時間 - D[i])。總扣分 = dp[pre].score + 扣分。取最小值，若相等則選字典序較小的（因科目名已排序，索引較小者優先）。

路徑重構

從全集狀態 (1<<N)-1 回溯 last 和 pre，將作業索引壓入棧，最後彈出輸出即為正確順序。

代碼實現（C++）

#include <iostream>
#include <vector>
#include <stack>
#include <string>
#include <algorithm>
using namespace std;

struct Homework { string name; int d, c; };
struct DPState { int score = 0x3f3f3f3f, time = 0, last = -1, pre = -1; };

int main() {
    int T; cin >> T;
    while (T--) {
        int N; cin >> N;
        vector<Homework> hw(N);
        for (int i = 0; i < N; ++i) cin >> hw[i].name >> hw[i].d >> hw[i].c;
        int ALL = 1 << N;
        vector<DPState> dp(ALL);
        dp[0].score = 0;
        for (int mask = 1; mask < ALL; ++mask) {
            for (int i = N-1; i >= 0; --i) if (mask & (1<<i)) {
                int pre = mask ^ (1<<i);
                int finish = dp[pre].time + hw[i].c;
                int penalty = max(0, finish - hw[i].d);
                int total = dp[pre].score + penalty;
                if (total < dp[mask].score || (total == dp[mask].score && i < dp[mask].last)) {
                    dp[mask].score = total;
                    dp[mask].time = finish;
                    dp[mask].last = i;
                    dp[mask].pre = pre;
                }
            }
        }
        cout << dp[ALL-1].score << '\n';
        stack<int> st;
        for (int m = ALL-1; m; m = dp[m].pre) st.push(dp[m].last);
        while (!st.empty()) { cout << hw[st.top()].name << '\n'; st.pop(); }
    }
    return 0;
}

關鍵點

• 狀態數 2^15 = 32768，轉移 O(N)，總複雜度 O(N·2^N) 約 50 萬，極快。
• 為保證字典序最小，枚舉 i 時從大到小（或從小到大但比較索引），利用科目名已排序的性質。