POJ 2068

就是必胜点与必败点的计算而已。计算每一种情况。设st[i][j]为在第i个人剩下j个石头时的情况，拿它转移后的情况比较。可以到达必败点，则当前为必胜点。若只能到达必胜点，则当前点为必败点。

 1 #include <iostream>
 2 #include <cstdio>
 3 using namespace std;
 4 const int S=8330;
 5 const int N=22;
 6 
 7 int st[N][S];
 8 int s,n;
 9 int MA[N];
10 
11 int main(){
12     int k,i,j;
13     while(scanf("%d",&k)!=EOF){
14         if(!k) break;
15         scanf("%d",&s);
16         n=2*k;
17         for(i=1;i<=n;i++)
18         scanf("%d",&MA[i]);
19         for(i=1;i<=n;i++)
20         st[i][0]=1;
21         for(j=1;j<=s;j++){
22             for(i=1;i<=n;i++){
23                 st[i][j]=0;
24                 if(i==n){
25                     for(k=1;k<=MA[i];k++){
26                         if(j-k>=0){
27                             if(st[1][j-k]==0){
28                                 st[i][j]=1;
29                                 break;
30                             }
31                         }
32                         else break;
33                     }
34                 }
35                 else{
36                     for(k=1;k<=MA[i];k++)
37                     if(j-k>=0){
38                         if(st[i+1][j-k]==0){
39                         st[i][j]=1;
40                         break;
41                         }
42                     }
43                     else break;
44                 }
45             }
46         }
47         printf("%d
",st[1][s]);
48     }
49     return 0;
50 }

View Code