poj 2068 NIM 博弈+dp

     博弈题关键要把握3个基本属性：

      1.确定末状态N,P状态

      2.一定存在至少一种抉择使N->P

      3.所有P->N

      实现形式随意，这题是用记忆化搜索来实现

/*
author:jxy
lang:C/C++
university:China,Xidian University
**If you need to reprint,please indicate the source**
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
int dp[21][9000];
int c[21];
int N;
int dfs(int now,int remain) //返回1代表当前这种状态这队必赢
{
    if(now>=N)now-=N;
    if(~dp[now][remain])return dp[now][remain];
    if(!remain)
        return dp[now][remain]=1;
    dp[now][remain]=0;
    int Min=min(c[now],remain);
    for(int i=1;i<=Min;i++)
        if(!dfs(now+1,remain-i))
            dp[now][remain]=1;
    return dp[now][remain];
}
int main()
{
    int n;
    while(~scanf("%d",&n)&&n)
    {
        N=n<<1;
        int s;
        scanf("%d",&s);
        memset(dp,-1,sizeof(dp));
        for(int i=0;i<N;i++) scanf("%d",&c[i]);
        printf("%d\n",dfs(0,s));
    }
}