UVA 10404 Bachet's Game：完全背包與博弈論

問題描述

有 n 塊石子，兩人輪流取走，每次必須從給定的 m 個數字集合中選擇一個數取走對應數量的石子（集合中必含 1）。取走最後一塊石子者獲勝。Stan 先手，雙方均採取最優策略，判斷勝者。

解題思路

這是典型的博弈論 DP 問題，狀態 dp[i] 表示剩餘 i 塊石子時先手是否必勝（1 必勝，0 必敗）。轉移：若存在合法取法 k 使得 dp[i - k] == 0，則 dp[i] = 1；否則 dp[i] = 0。因為石子可重複取，屬於完全背包類型。n ≤ 1,000,000，m ≤ 10，O(n*m) 可接受。

代碼實現 (C++)

#include 
using namespace std;
const int MAXN = 1000005;
int moves[15];
bool dp[MAXN];

int main() {
    int n, m;
    while (scanf("%d%d", &n, &m) == 2) {
        for (int i = 0; i < m; ++i) scanf("%d", &moves[i]);
        memset(dp, 0, sizeof(dp));
        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (i >= moves[j] && !dp[i - moves[j]]) {
                    dp[i] = true;
                    break;
                }
            }
        }
        puts(dp[n] ? "Stan wins" : "Ollie wins");
    }
    return 0;
}

複雜度分析

• 時間複雜度：O(n * m)，n ≤ 10^6，m ≤ 10，約 10^7 操作，極快。
• 空間複雜度：O(n)。

總結

Bachet's Game 是取石子遊戲的變體，核心在於博弈 DP 的狀態轉移。注意集合中必含 1 保證遊戲不會卡死。該模板可擴展到更多變體。