hdu4111 Alice and Bob 博弈论

本文主要是介绍hdu4111 Alice and Bob 博弈论，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：有N堆石子，每堆石子有一个数目，现有两个人博弈，每个人每次可以进行两个操作中的一个： 1、从某堆拿掉一个石子（若某堆石子为0了，那么这堆就不存在了）；2、合并两堆石子 没有操作的就输。问是哪个赢

统计1的个数c，以及非1情况下的步数s，包括合并。
c为奇数，s不等于2：那么先手必胜。
s为2或者为0：c为3的倍数是先手必败。
否则的话，s为奇数时先手必胜。
首先没有1的情况下很好证明，就是总的步数和为奇数时为先手必胜态，N点。相反，如果为偶数就是P点。（这种情况
下必胜的人只要保证任意一堆石子的个数不会小于2即可，直到最后只剩下一堆，因为1是一个比较特殊的存在）
再者证明奇数个1且s不为2的时候为必胜态，从一个1的开始，假设现在有一个1和s，如果s为奇数，那么先手可以合并
两堆石子；如果s是偶数，先手可以拿走1；所以这种情况下一定是先手必胜，因为移动1可以选择少掉一步或者两步。
那么现在就是两个1和s的情况，如果其中一个人先消耗掉一个1，和s合并，那么剩下的状态是(1,s+1)的N点；取走1，
剩下(1,s)同样是N点；合并两个1，(2,s)==>(s+3)的状态，如果s为奇数，那么即为P态，对应的刚才先手就是必胜，反之
则是必败，这种情况归纳到结论中的第三条。那么三个1的情况下就可以消耗一个1更变s的奇偶性。
不过在s=2或者s=0的时候属于特殊情况，因为2去掉一个之后就变成了1，s为0时为全1，通过上面的规律，我们已经知

实在是没想到，大家都说是简单的题目我做了一下午也没A掉他看别人思路看了很长时间。。。。。。真的很巧妙

       
3
3
1 1 2
2
3 4
3
2 3 5 

       
Case #1: Alice
Case #2: Bob
Case #3: Bob 

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int dp[55][55000];
int DP(int a,int b)
{if(dp[a][b]!=-1) return dp[a][b];if(b==1) return dp[a][b]=DP(a+1,0);//只剩一个单独的一，加入其它1中dp[a][b]=0;if(a>=1&&!DP(a-1,b))//直接去掉一个1dp[a][b]=1;if(a>=1&&b&&!DP(a-1,b+1))//将一个1合到其它数中dp[a][b]=1;if(a>=2&&((b&&!DP(a-2,b+3))||(b==0&&!DP(a-2,2))))//将2个1并起来dp[a][b]=1;if(b>=2&&!DP(a,b-1))//减小一dp[a][b]=1;return dp[a][b];
}
int main()
{int T;scanf("%d",&T);memset(dp,-1,sizeof(dp));for(int t=1; t<=T; t++){int n;scanf("%d",&n);int j,k,i;for( j=0,k=0,i=0; i<n; i++){int a;scanf("%d",&a);if(a==1)j++;elsek+=+a+1;}if(k);k--;DP(j,k);printf("Case #%d: ",t);if(dp[j][k]) printf("Alice\n");else printf("Bob\n");}return 0;
}

这篇关于hdu4111 Alice and Bob 博弈论的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！