POJ 2068 Nim

因为两边是不平等的，所以不能用QJYQ。那么这个数据范围这么小，我们可以直接搜索！

记\(f[i][j]\)为第\(i\)个人面对\(j\)颗石头是否会嬴。其实这本质上是一个逆推的过程。

#include<cstdio> 
#include<cstdlib>
#include<cstring>

int n, s, a[22], f[22][9000];

int read() {
	int x = 0, f = 1; char s;
	while((s = getchar()) > '9' || s < '0') {
		if(s == '-') f = -1;
		if(s == EOF) exit(0);
	}
	while(s >= '0' && s <= '9') {
		x = (x << 1) + (x << 3) + (s ^ 48);
		s = getchar();
	}
	return x * f;
}

int dfs(const int x, const int sum) {
	if(~ f[x][sum]) return f[x][sum];
	if(sum == 0) return f[x][sum] = 1;
	for(int i = 1; i <= a[x] && i <= sum; ++ i)
		if(dfs((x + 1) % n, sum - i) == 0)
			return f[x][sum] = 1;
	return f[x][sum] = 0;
}

int main() {
	while(n = read(), s = read()) {
		memset(f, -1, sizeof f);
		n <<= 1;
		for(int i = 0; i < n; ++ i) a[i] = read();
		printf("%d\n", dfs(0, s));
	}
	return 0;
}