HDU 5045 Contest：狀態壓縮 DP 求解最大期望得分

問題描述

N 個隊員（N ≤ 10），M 道題（M ≤ 1000），每人做每題需 1 小時，且任意時刻任兩人累計做題時間差不超過 1。即題目必須分成若干輪，每輪 N 道題（最後一輪可能不足），每輪內每人恰好做一題。已知每人做對每題的概率 P[i][j]，求最大期望得分。

狀態壓縮 DP 設計

狀態定義：dp[i][mask] 表示前 i 道題已安排，當前輪次中「已做題隊員集合」為 mask（bit k=1 表示第 k 人已在本輪做過題）的最大期望值。
狀態空間：i ∈ [0, M], mask ∈ [0, 2^N)，共 (M+1) * 2^N ≤ 1001 * 1024 ≈ 10^6 狀態。

轉移邏輯

• 初始 dp[0][0] = 0，其餘 -inf。
• 第 i 題（0-indexed）考慮分配給哪位隊員 k：
  • 若 mask 第 k 位為 0（本輪未做過），可轉移：
  newMask = mask | (1<<k)
if (newMask == (1<<N)-1) newMask = 0; // 本輪結束，重置
dp[i+1][newMask] = max(dp[i+1][newMask], dp[i][mask] + P[k][i]);
• 答案為 max_{mask} dp[M][mask]。

參考代碼（C++）

const int MAXM = 1005, MAXS = 1 << 10;
double P[10][MAXM];
double dp[MAXM][MAXS];

int main() {
    int T; scanf("%d", &T);
    for (int cas = 1; cas <= T; ++cas) {
        int n, m; scanf("%d%d", &n, &m);
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < m; ++j)
                scanf("%lf", &P[i][j]);

        int full = (1 << n) - 1;
        for (int i = 0; i <= m; ++i)
            for (int s = 0; s <= full; ++s)
                dp[i][s] = -1e100;
        dp[0][0] = 0;

        for (int i = 0; i < m; ++i) {
            for (int s = 0; s <= full; ++s) if (dp[i][s] > -1e50) {
                for (int k = 0; k < n; ++k) if (!(s & (1<<k))) {
                    int ns = s | (1<<k);
                    if (ns == full) ns = 0;
                    dp[i+1][ns] = max(dp[i+1][ns], dp[i][s] + P[k][i]);
                }
            }
        }

        double ans = 0;
        for (int s = 0; s <= full; ++s) ans = max(ans, dp[m][s]);
        printf("Case #%d: %.5lf\n", cas, ans);
    }
    return 0;
}

關鍵優化與細節

• 初始化：用極小負數（如 -1e100）標記不可達狀態，避免 -inf 運算產生 NaN。
• 輪次重置：newMask == full 時歸零，體現「時間差不超過 1」的硬約束。
• 浮點輸出：%.5lf 保留 5 位小數，符合題目要求。
• 複雜度：O(M * 2^N * N) ≈ 1000 * 1024 * 10 = 10^7，極易通過 2s 時限。

常見誤區

1. 以為每輪順序固定：實際上每輪內 N 人順序可任意排列，DP 自然枚舉了所有排列。
2. 忘記最後一輪可能不完整：mask 不歸零也合法，答案取所有 mask 最大值即可涵蓋。
3. 概率矩陣讀取順序：題目給 N 行 M 列，P[i][j] 表示第 i 人第 j 題，代碼中第二維對應題目索引。

總結

HDU 5045 是狀壓 DP 經典應用：將「時間差約束」轉化為「輪次內每人恰做一次」的集合狀態，狀態數隨 N 指數增長但 N≤10 使其完全可行。掌握「輪次重置」技巧與浮點 DP 初始化細節，即可穩健求解。