【POJ】【2068】Nim

博弈论/DP

  这是Nim?这不是巴什博奕的变形吗……

  我也不会捉啊,不过一看最多只有20个人,每人最多拿16个石子,总共只有8196-1个石子,范围好像挺小的,嗯目测暴力可做。

  so,记忆化搜索直接水过去了……

  出口应该很好判断:当前只有一个石子的时候输,石子数<=m[i]+1则赢(保证拿完后只给对方留一个)

 Source Code
Problem: User: sdfzyhy
Memory: 1416K Time: 32MS
Language: G++ Result: Accepted Source Code //POJ 1000
#include<cmath>
#include<queue>
#include<vector>
#include<string>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define rep(i,n) for(int i=0;i<n;++i)
#define F(i,j,n) for(int i=j;i<=n;++i)
#define D(i,j,n) for(int i=j;i>=n;--i)
using namespace std; int getint(){
int r=,c=; char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if (ch=='-') c=-;
for(;isdigit(ch);ch=getchar()) r=r*+ch-'';
return r*c;
}
const int N=,INF=~0u>>;
const double eps=1e-;
/******************template***********************/
#define debug
int n,m,a[];
bool vis[][],dp[][];
bool f(int x,int y){
if (vis[x][y]) return dp[x][y];
vis[x][y]=;
if (y==) return dp[x][y]=;
if (y<=a[x]+) return dp[x][y]=; int next;
if (x==n*) next=;
else next=x+;
F(i,,a[x]) if (f(next,y-i)==) return dp[x][y]=;
return dp[x][y]=;
} int main(){
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
#endif
while(scanf("%d",&n)!=EOF && n){
m=getint();
F(i,,n<<) a[i]=getint();
memset(vis,,sizeof vis);
memset(dp,,sizeof (dp));
printf("%d\n",f(,m));
// F(i,1,n<<1) F(j,1,m) printf("f(%d,%d)=%d\n",i,j,dp[i][j]);
}
return ;
}
上一篇:PHP漏洞全解


下一篇:三重for循环实现对二维数组的按列排序(JavaScript)