本文主要是介绍ZOJ 3057 Beans Game题解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
【题目大意】：
有三堆豆子a,b,c(0<a+b+c<=300)。TT和DD轮流从其中一堆拿走任意个豆子或从其中的两种拿走同样多的豆子，最后一个拿完的获胜。（TT先手）
【分析】：
首先想到的是记忆化搜索，但是由于常数过大，以及空间复杂度的问题，改成利用“能操作成必败态的局面必为必胜态”的性质，改用常数更小的递推形式。具体请见代码（附记忆化搜索的代码和递推代码，只有递推能过）
【代码1：记忆化搜索】：
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define MAX 301
int A,B,C,rem[MAX][MAX][MAX];
int work(int a,int b,int c)
{if(rem[a][b][c]!=-1) return rem[a][b][c]; if((a&&!b&&!c) || (!a&&b&&!c) || (!a&&!b&&c) || (a==b&&!c) || (a==c&&!b) || (c==b&&!a))return rem[a][b][c]=1;for(int i=1;i<=a;i++)if(!rem[a-i][b][c] || work(a-i,b,c)==0)return rem[a][b][c]=1;for(int i=1;i<=b;i++)if(!rem[a][b-i][c] || work(a,b-i,c)==0)return rem[a][b][c]=1;for(int i=1;i<=c;i++)if(!rem[a][b][c-i] || work(a,b,c-i)==0)return rem[a][b][c]=1;int limit;limit=a<b?a:b;for(int i=1;i<=limit;i++)if(!rem[a-i][b-i][c] || work(a-i,b-i,c)==0)return rem[a][b][c]=1;limit=b<c?b:c;for(int i=1;i<=limit;i++)if(!rem[a][b-i][c-i] || work(a,b-i,c-i)==0)return rem[a][b][c]=1;limit=a<c?a:c;for(int i=1;i<=limit;i++)if(!rem[a-i][b][c-i] || work(a-i,b,c-i)==0)return rem[a][b][c]=1;return rem[a][b][c]=0;
}
int main()
{memset(rem,-1,sizeof(rem));while(scanf("%d%d%d",&A,&B,&C)!=EOF){if(work(A,B,C)==1)printf("1\n");else printf("0\n");}return 0;
} 【代码2：递推】：
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define MAX 301
int A,B,C;
bool rem[MAX][MAX][MAX];
void work()
{for(int a=0;a<=300;a++)for(int b=0;b<=300;b++)for(int c=0;c<=300;c++)if(!rem[a][b][c]){for(int i=1;a+i<=300;i++)rem[a+i][b][c]=true;for(int i=1;b+i<=300;i++)rem[a][b+i][c]=true;for(int i=1;c+i<=300;i++)rem[a][b][c+i]=true;int limit=a<b?b:a;for(int i=1;limit+i<=300;i++)rem[a+i][b+i][c]=true;limit=a<c?c:a;for(int i=1;limit+i<=300;i++)rem[a+i][b][c+i]=true;limit=b<c?c:b;for(int i=1;limit+i<=300;i++)rem[a][b+i][c+i]=true;}
}
int main()
{work();while(scanf("%d%d%d",&A,&B,&C)!=EOF){printf("%d\n",rem[A][B][C]);}return 0;
} 这篇关于ZOJ 3057 Beans Game题解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
