http://codevs.cn/problem/3153/
对于这道题,直觉告诉我每一个状态一定是必胜或必败的
然后设定操作次数t,t为取完些石子最多需要多少步。
如果\(a_i\)不为1,\(t=\sum a_i+n-1\)。因为每次只让操作数减一。
但因为有\(a_i\)为1的情况,可以直接让操作数减二,所以我们把石子数为1的堆数和剩下的石子堆的操作数作为状态进行记忆化搜索。
正如xiaoyimi所说,细节确实很多QaQ
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 53;
const int M = 50003;
int in() {
int k = 0, fh = 1; char c = getchar();
for(; c < '0' || c > '9'; c = getchar())
if (c == '-') fh = -1;
for(; c >= '0' && c <= '9'; c = getchar())
k = k * 10 + c - 48;
return k * fh;
}
int n, a, cnt, sum;
bool vis[M][N], f[M][N];
bool pd(int tot, int num) {
if (vis[tot][num]) return f[tot][num];
vis[tot][num] = true;
if (tot == 1) return f[tot][num] = pd(0, num + 1);
if (num >= 1 && !pd(tot, num - 1)) return f[tot][num] = true;
if (num >= 2 && !pd(tot + 2 + (tot > 0), num - 2)) return f[tot][num] = true;
if (tot >= 2 && !pd(tot - 1, num)) return f[tot][num] = true;
if (num >= 1 && tot != 0 && !pd(tot + 1, num - 1)) return f[tot][num] = true;
return false;
}
int main() {
int T; T = in();
while (T--) {
n = in(); sum = cnt = 0;
for(int i = 1; i <= n; ++i) {
a = in();
if (a == 1) ++cnt;
else sum += a + 1;
}
if (sum) --sum;
puts(pd(sum, cnt) ? "YES" : "NO");
}
return 0;
}