题目描述 DD 和 MM 正在玩取石子游戏。他们的游戏规则是这样的：桌上有若干石子，DD 先取，轮流取，每次必须取质数个。如果某一时刻某一方无法从桌上的石子中取质数个，比如说剩下 0 个或 1 个石子，那么他/她就输了。 DD 和 MM 都很聪明，不管哪方存在一个可以必胜的最优策略，他/她都会按照最优策略保证胜利。于是，DD 想知道，对于给定的桌面上的石子数，他究竟能不能取得胜利呢？ 当 DD 确定会取得胜利时，他会说：“不管 MM 选择怎样的取石子策略，我都能保证至多 X 步以后就能取得胜利。”那么，最小的满足要求的 X 是多少呢？注意，不管是 DD 取一次石子还是 MM 取一次石子都应该被计算为“一步”。 输入格式 第一行有一个整数 N，表示这个输入文件中包含 N 个测试数据。 第二行开始，每行有一个测试数据，其中仅包含一个整数，表示桌面上的石子数。 输出格式 你需要对于每个输入文件中的 N 个测试数据输出相应的 N 行。 如果对于该种情形是 DD 一定取得胜利，那么输出最小的 X。否则该行输出 -1。
一道比较水（对各位dalao来说）的博弈论，很明显我只能写爆搜了= = 显然的质数表+简单博弈论模型； 于是80分；
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <cstdio> #include <vector> using namespace std; typedef unsigned long long ull; typedef long long ll; bool vis[20001]; int prime[5001]; int dp[20001][2]; void getprime() { memset(vis,0,sizeof(vis)); int cnt=0; for(int i=2;i<=20000;i++) { if(!vis[i]) { prime[++cnt]=i; dp[prime[cnt]][0]=1; dp[prime[cnt]+1][0]=1; dp[prime[cnt]][1]=-1; dp[prime[cnt]+1][1]=-1; for(int j=2;j*i<=20000;j++) vis[j*i]=1; } } } void pre() { for(int i=1;i<=20000;i++) { dp[i][0]=dp[i][1]=-2; } dp[0][1]=0; dp[1][1]=0; dp[0][0]=-1; dp[1][0]=-1; } void dfs(int state,int person) { if(dp[state][person]!=-2) return; if(person==1) { for(int i=1;prime[i]<=state;i++) { dfs(state-prime[i],0); if(dp[state-prime[i]][0]==-1) { dp[state][person]=-1; return ; } dp[state][person]=max(dp[state-prime[i]][0]+1,dp[state][person]); } if(dp[state][person]<-2) dp[state][person]=-1; } else { dp[state][person]=0x3fffff00; for(int i=1;prime[i]<=state;i++) { dfs(state-prime[i],1); if(dp[state-prime[i]][1]==-1) continue; dp[state][person]=min(dp[state-prime[i]][1]+1,dp[state][person]); } if(dp[state][person]==0x3fffff00) dp[state][person]=-1; } } int main() { int t; scanf("%d",&t); pre(); getprime(); while(t--) { int n; scanf("%d",&n); dfs(n,0); printf("%d\n",dp[n][0]); } return 0; }