POJ2068 Nim 博弈论 dp
http://poj.org/problem?id=2068
博弈论的动态规划，依然是根据必胜点和必输点的定义，才明白过来博弈论的dp和sg函数差不多完全是两个概念（前者包含后者），sg函数只是mex操作处理多个博弈游戏的一种方法，mdzz要改以前的标签了。
f [ i ] [ j ] [ k ] 表示: i队伍在第j个队员取前还剩下k个石头的状态为i队伍必胜还是必输。
代码
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #include<cmath> 5 #include<iostream> 6 #include<map> 7 #include<ctime> 8 using namespace std; 9 const int maxn=1<<13; 10 int f[2][20][maxn+1]={}; 11 int a[2][maxn]={}; 12 int n,m; 13 int main(){ 14 while(~scanf("%d",&n)){ 15 if(!n)break; 16 scanf("%d",&m); 17 for(int i=1;i<=2*n;i++){ 18 scanf("%d",&a[i&1][(i+1)/2]); 19 } 20 memset(f,0,sizeof(f)); 21 for(int i=0;i<=m;i++){//面对的还剩几个 22 for(int j=0;j<2;j++){//队伍 23 for(int k=1;k<=n;k++){//第几人 24 if(i==0){ 25 f[j][k][i]=1; 26 continue; 27 }f[j][k][i]=0; 28 int z=j^1; 29 int zz=j?k:(k==n?1:k+1); 30 for(int w=1;w<=a[j][k];w++){ 31 if(i<w)break; 32 if(!f[z][zz][i-w]){ 33 f[j][k][i]=1; 34 break; 35 } 36 } 37 } 38 } 39 } 40 printf("%d ",f[1][1][m]); 41 } 42 return 0; 43 }