有 N ≤ 15 個作業，每個有截止天數 D 和所需天數 C。按順序做作業，完成時間超過截止天數的部分每天扣 1 分。求最小總扣分及字典序最小的作業順序。
dp[mask]：已完成作業集合為 mask 時的最小扣分、總耗時、前驅決策2^15 = 32768，完全可行mask 嘗試添加未做的作業 i
time' = dp[mask].time + C[i]score' = dp[mask].score + max(0, time' - D[i])score' < dp[mask|(1< 或扣分相同時字典序更小，則更新 題目保證輸入已按學科名字典序排列。為得到字典序最小的最優解：
struct State {
int pre = -1; // 前驅作業索引
int time = 0; // 總耗時
int score = INF; // 總扣分
} dp[1<<15];
struct Homework { string name; int d, c; } hw[15];
int main() {
int T; cin >> T;
while (T--) {
int n; cin >> n;
for (int i = 0; i < n; ++i) cin >> hw[i].name >> hw[i].d >> hw[i].c;
int ALL = 1 << n;
fill(dp, dp + ALL, State());
dp[0].score = 0;
for (int mask = 0; mask < ALL; ++mask) {
if (dp[mask].score == INF) continue;
for (int i = 0; i < n; ++i) if (!(mask & (1<
關鍵優化與避坑
- 初始化
dp[0].score = 0，其餘 INF
- 利用
mask 從小到大遍歷天然保證字典序最小（輸入已排序）
- 回溯時用
mask ^= (1< 回退
- 時間複雜度
O(n·2^n)，n=15 约 50 萬狀態轉移，極快
