POJ 1440：三維 DP 解決甜甜圈博弈遊戲

題目大意

n 個甜甜圈，每次取 1~m 個。Steve 和 Digit 輪流取，取完者吃掉自己手中甜甜圈，對手的甜甜圈重新放回。下一輪對手先手。求 Steve 最大能吃多少個。n,m ≤ 100。

狀態定義

`d[i][j][u][p]`：總共 i 個甜甜圈，剩 j 個未取，Steve 手中 u 個，下一步玩家 p (0=Steve, 1=Digit) 時，**Steve 最終能吃到的最大數**。

轉移方程

**Steve 回合 (p=0)：**

• 取 v 個 (1≤v≤min(m,j))：
  • 若 v < j：Steve 手中變 u+v，剩 j-v，轉 Digit 回合。Steve 最終得 `i - d[i][j-v][u+v][1]` (總數減去 Digit 能拿到的)。
  • 若 v == j：Steve 取走所有剩餘，吃掉 u+j，對手歸還 q=i-j-u 個。新遊戲總數 q，Steve 手中 0，剩 q，對手先手。Steve 最終得 `i - d[q][q][0][1]`。
• 取最大值：`d[i][j][u][0] = max(...)`

**Digit 回合 (p=1)：** 同理，Digit 手中 q = i-j-u。

• 取 v < j：`d[i][j][u][1] = max(i - d[i][j-v][u][0])`
• 取 v = j：`d[i][j][u][1] = max(i - d[q][q][0][0])` (q=i-j-u)

代碼實現 (C++)

#include 
#include 
using namespace std;

int d[103][103][103][2];

int main() {
    int n, m;
    while (~scanf("%d%d", &n, &m)) {
        d[0][0][0][0] = d[0][0][0][1] = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                int p = i - j; // 已取總數
                for (int u = 0; u <= p; u++) {
                    int q = p - u; // Digit 手中數
                    // Steve 回合
                    int best = 0;
                    for (int v = 1; v <= m; v++) {
                        if (v > j) break;
                        if (v == j) best = max(best, i - d[i-u-v][i-u-v][0][1]);
                        else best = max(best, i - d[i][j-v][u+v][1]);
                    }
                    d[i][j][u][0] = best;
                    // Digit 回合
                    best = 0;
                    for (int v = 1; v <= m; v++) {
                        if (v > j) break;
                        if (v == j) best = max(best, i - d[i-q-v][i-q-v][0][0]);
                        else best = max(best, i - d[i][j-v][u][0]);
                    }
                    d[i][j][u][1] = best;
                }
            }
        }
        printf("%d\n", d[n][n][0][0]);
    }
    return 0;
}

複雜度分析

• 狀態數：O(n³) ≈ 100³ = 1e6。
• 轉移：O(m) ≤ 100。
• 總操作：O(n³ m) ≈ 1e8，邊界可行 (優化常數可過)。
• 空間：103⁴ × 4 bytes ≈ 40MB，接近限制可用 `short` 或滾動數組優化。

關鍵洞察

博弈雙方目標對立，`d` 定義為 Steve 最終所得，轉移時用「總數 - 對手最優所得」體現零和博弈本質。