放牧代码和思想
专注自然语言处理、机器学习算法
    博主不用扣扣,公事请博客留言,私事请微博私信。开源项目一律GitHub见,发错地方恕不回复,谢谢。

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

目录

挑战程序设计竞赛.jpg

Cheat in the Game 

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

现在先手玩家贿♂赂了你,请你帮他构造必胜条件。游戏中的卡片是固定的,但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;
}
14946368 hankcs 3688 Accepted 368K 2516MS C++ 1132B 2015-11-26 13:50:00

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

分享到:更多 ()

评论 欢迎留言

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

我的开源项目

HanLP自然语言处理包基于DoubleArrayTrie的Aho Corasick自动机