首页 > 代码库 > POJ 3688 Cheat in the Game（博弈论）
POJ 3688 Cheat in the Game（博弈论）
【题目链接】 http://poj.org/problem?id=3688
【题目大意】
有俩人玩一个取石子的游戏，你是裁判。
游戏中有W块石头和N张卡片，卡片上分别写着数字Ai。
玩家随机抽走一张卡片，按卡片上的数字从石头堆中取走相应数量的石头，
如果石头不够，玩家重新抽卡片，取走最后一块石头的玩家获胜；
如果石头堆为空仍然未分出胜负，则拿回所有石头和卡片重新开始。
现在先手玩家贿赂了你，请你帮他构造必胜条件。
游戏中的卡片是固定的，但W可供你操作。问有多少小于或等于M的W满足要求。
【题解】
我们发现如果石头的数量可以仅能被奇数个数字组成，那么先手一定能赢，
如果仅能被偶数组成，那么后手一定能赢，如果既可以被奇数组成又能被偶数组成，
那么两者都有可能赢，现在求必胜布局，所以我们找出只能被奇数个数字组成的状态即可。
【代码】
#include <cstdio>#include <algorithm>#include <cstring> using namespace std;int a[100010],n,m;bool dp[100010][2];int main(){ while(~scanf("%d%d",&n,&m),n+m){ for(int i=0;i<n;i++)scanf("%d",&a[i]); sort(a,a+n); memset(dp,0,sizeof(dp)); dp[a[0]][1]=1; for(int i=1;i<n;i++){ for(int j=m;j>a[i];j--){ if(dp[j-a[i]][0])dp[j][1]=1; if(dp[j-a[i]][1])dp[j][0]=1; }dp[a[i]][1]=1; }int ans=0; for(int i=1;i<=m;i++){ if(dp[i][1]&&!dp[i][0])ans++; }printf("%d\n",ans); }return 0;}POJ 3688 Cheat in the Game（博弈论）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。