题目大意：
有2n个人，从0开始编号，按编号奇偶分为两队，循环轮流取一堆有m个石子的石堆，偶数队先手，每个人至少取1个，至多取w[i]个，取走最后一个石子的队伍输。问偶数队是否能赢。
分析：
题目数据不大很容易就可以联想到DP博弈，设dp[i][j]表示轮到第i个人，还有j个石子的情况下他所属队伍是否能赢。
那么如果存在一个x，使第i个人取了x个石子后第(i+1)%2n个人无论如何都败，那么他就可以赢；若不存在则输。即是：
dp[i][j]=(dp[(i+1)%2n][j-1]&dp[(i+1)%2n][j-2]&……&dp[(i+1)%2n][j-w[i]])^1;
由于有循环，所以直接dp不好做，改用记忆化搜索。
#include<stdio.h> #include<string.h> int dp[21][100000],a[21],n; int dfs(int id , int val) { if(val==0) return dp[id][val]=1; if(dp[id][val]!=-1) return dp[id][val]; dp[id][val]=0; for(int i=1 ; i<=a[id] ; i++) { if(val<i) break; if(!dfs((id+1)%(2*n),val-i)) dp[id][val]=1; } return dp[id][val]; } int main( ) { int m; while(scanf("%d",&n)!=EOF) { if(n==0) break; scanf("%d",&m); for(int i=0 ; i<2*n ; i++) scanf("%d",&a[i]); memset(dp,-1,sizeof(dp)); printf("%d ",dfs(0,m)); } }