UVa 11125 Arrange Some Marbles：多維 DP 計數排列方案

題目

n 種顏色玻璃珠 (n≤4)，每種數量 0~7。排成一行，相同顏色相鄰形成組，組大小 1~3。相鄰組顏色不同且大小不同，首尾組也須顏色不同且大小不同。求合法排列數。

狀態定義

DP 狀態：dp[firstColor][firstSize][c1][c2][c3][c4][lastColor][lastSize]
含義：第一組顏色 firstColor 大小 firstSize，剩餘各顏色數量 c1..c4，最後一組顏色 lastColor 大小 lastSize 的合法排列數。
狀態總數 ≤ 4×3×8^4×4×3 ≈ 1.2M，配合記憶化可行。

遞歸轉移

ll dfs(int firstC, int firstS, int c1, int c2, int c3, int c4, int lastC, int lastS) {
    if (c1==0 && c2==0 && c3==0 && c4==0) {
        // 所有珠用完，檢查首尾約束
        return (lastC != firstC && lastS != firstS) ? 1 : 0;
    }
    if (memo[...] != -1) return memo[...];
    ll ans = 0;
    // 嘗試添加下一組，顏色 ≠ lastC，大小 ≠ lastS，數量足夠
    for (int color = 1; color <= 4; ++color) if (color != lastC) {
        int* cnt = (color==1?&c1:color==2?&c2:color==3?&c3:&c4);
        for (int sz = 1; sz <= 3; ++sz) if (sz != lastS && *cnt >= sz) {
            *cnt -= sz;
            ans += dfs(firstC, firstS, c1, c2, c3, c4, color, sz);
            *cnt += sz;
        }
    }
    return memo[...] = ans;
}

初始調用

枚舉第一組顏色與大小，調用 DFS，累加總數。特判：所有數量為 0 時答案為 1 (空排列)。

複雜度

• 狀態數 ~10^6，每狀態轉移 ≤ 3×3=9 次
• 總時間 ~10^7 操作，3000 測試用例預計算一次後 O(1) 回答

關鍵優化

• 用靜態陣列 dp[5][9][9][9][9][9][5][9] 替代 map，極快。
• 顏色數 n≤4，缺失顏色視為數量 0 統一處理。