hdu4111 Alice and Bob---sg dp记忆化求sg

Alice and BobTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 598 Accepted Submission(s): 207


Problem DescriptionInputOutputSample InputSample OutputSource/*题意：有N堆石子，每堆石子有一个数目，现有两个人博弈，每个人每次可以进行两个操作中的一个：1、从某堆拿掉一个石子（若某堆石子为0了，那么这堆就不存在了）；2、合并两堆石子没有操作的就输。问是哪个赢思想：如果每堆石子数都大于1，那么最后结果肯定相当于所有的堆合并成一堆后，然后再一个一个拿掉的结果。因为如果那种情况是赢的人一定会不断合并堆来确保他是赢的。又因为所有堆的石子数都大于1，所以输的人无法阻止他这么干。而有些堆石子数等于1的话，就不一定是所有的合并的结果了，因为输的人可以直接把等于1的堆去掉，就破坏了结构（合并相当于2步，去掉只需要1步）。dp[i][j]表示有i个石子数为1的堆数，其它堆合并再取完的步数为j。若值为1则先取者胜，为0为先取者输*/#include<stdio.h>#include<string.h>#include<iostream>#include<algorithm>using namespace std;int dp[55][55000];int a[55];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(){memset(dp,-1,sizeof(dp));int t,test=1,n,i,j,k;scanf("%d",&t);while(t--){scanf("%d",&n);for(j=0,k=0,i=0;i<n;i++){scanf("%d",&a[i]);if(a[i]==1) j++;else k+=a[i]+1;//+1是因为要合并，多一步}if(k) k--;//合并的次数多算了一次DP(j,k);printf("Case #%d: ",test++);if(dp[j][k]) printf("Alice\n");else printf("Bob\n");}return 0;}