671
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));
}
}
最後更新：2017-04-03 16:49:07