POJ 3688 Cheat in the Game 题解《挑战程序设计竞赛》

Cheat in the Game 

金手指：有俩人玩一个取石子的游戏，你是裁判。游戏中有W块石头和N张卡片，卡片上分别写着数字A_i。玩家随机抽走一张卡片，按卡片上的数字从石头堆中取走相应数量的石头，如果石头不够，玩家重新抽卡片，取走最后一块石头的玩家获胜；如果石头堆为空仍然未分出胜负，则拿回所有石头和卡片重新开始。

现在先手玩家贿♂赂了你，请你帮他构造必胜条件。游戏中的卡片是固定的，但W可供你操作。问有多少小于或等于M的W满足要求。

4.2找出游戏的必胜策略 

推理与动态规划算法 

如果W只能表示成特定的n张卡片上的数字之和，那么：

• 当n为偶数时，{先手一张，后手一张}循环n/2次拿完石头，后手玩家必胜。

• 当n为奇数时，{先手一张，后手一张}循环n/2 + 1次拿完石头，先手玩家必胜。

如果W既可以表示成奇数张卡片数字之和，也可以表示成偶数张卡片数字之和，则两人都可能获胜；或者说没有必胜决策。

如果W既无法表示成奇数张卡片数字之和，也无法表示成偶数张卡片数字之和，则W无法用卡片取完，两人会一直玩到天荒地老，你这个裁判就变成了灯泡，而且是长明灯。

所以对题目有用的只有第一个如果分支。

动态规划地搜索整个M范围，定义

bool dp[100000 + 16][2]; // dp[W][0]=true表示W可以分解成偶数个数；dp[W][1]=true表示W可以分解成奇数个数

则

if (dp[j - A[i]][0])
    dp[j][1] = true;    // 偶数+1=奇数
if (dp[j - A[i]][1])
    dp[j][0] = true;    // 奇数+1=偶数

满足

if (dp[i][1] && !dp[i][0])  // 只能表示成奇数

的就是符合要求的一个W。

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

int A[10000 + 16];
bool dp[100000 + 16][2]; // dp[W][0]=true表示W可以分解成偶数个数；dp[W][1]=true表示W可以分解成奇数个数

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif
    int N, M;
    while (scanf("%d%d", &N, &M), N)
    {
        for (int i = 0; i < N; ++i)
        {
            scanf("%d", A + i);
        }
        sort(A, A + N);
        memset(dp, 0, sizeof(dp));
        dp[A[0]][1] = true;     // W=A_0可以由A_0这一个数构成
        for (int i = 1; i < N; ++i)
        {
            for (int j = M; j > A[i]; --j)
            {
                if (dp[j - A[i]][0])
                    dp[j][1] = true;    // 偶数+1=奇数
                if (dp[j - A[i]][1])
                    dp[j][0] = true;    // 奇数+1=偶数
            }
            dp[A[i]][1] = true;         // W=A_i可以由A_i这一个数构成
        }
        int ans = 0;
        for (int i = 1; i < M + 1; ++i)
        {
            if (dp[i][1] && !dp[i][0])  // 只能表示成奇数
                ++ans;
        }
        printf("%d\n", ans);
    }
#ifndef ONLINE_JUDGE
    fclose(stdin);
#endif
    return 0;
}

 知识共享署名-非商业性使用-相同方式共享：码农场 » POJ 3688 Cheat in the Game 题解《挑战程序设计竞赛》