46 lines
1.5 KiB
C++
46 lines
1.5 KiB
C++
#include <bits/stdc++.h>
|
||
using namespace std;
|
||
const int N = 55, M = 50060;
|
||
int n, f[N][M];
|
||
|
||
int dfs(int a, int b) {
|
||
if (~f[a][b]) return f[a][b]; // 记忆化搜索
|
||
int &v = f[a][b]; // 引用，赋值更快捷
|
||
if (!a) return b & 1; // a==0时，看b是不是奇数，奇数必胜，否则必败
|
||
|
||
if (b == 1) return dfs(a + 1, b - 1);
|
||
if (a && !dfs(a - 1, b)) return v = 1; // 从左边取一石子:左侧不空，并且取完后整体是一个必败态,那我必胜
|
||
if (b && !dfs(a, b - 1)) return v = 1; // 合并b
|
||
if (a && b > 1 && !dfs(a - 1, b + 1)) return v = 1; // 合并a,b各一个
|
||
if (a > 1 && !dfs(a - 2, b == 0 ? b + 2 : b + 3)) return v = 1; // 合并a
|
||
return v = 0;
|
||
}
|
||
int main() {
|
||
int T;
|
||
cin >> T;
|
||
memset(f, -1, sizeof f); // 初始化DP数组，-1
|
||
|
||
// 边界初始化
|
||
f[1][0] = f[2][0] = 1;
|
||
f[3][0] = 0;
|
||
|
||
while (T--) {
|
||
cin >> n;
|
||
int a = 0, b = -1;
|
||
for (int i = 1; i <= n; i++) {
|
||
int x;
|
||
cin >> x;
|
||
if (x == 1)
|
||
a++; // 左侧石子个数为1的石子堆数量
|
||
else
|
||
b += x + 1; // 1:新增加1堆，x:这一堆x个
|
||
}
|
||
if (b < 0) b = 0; // 一堆都没有，b=0
|
||
|
||
if (dfs(a, b))
|
||
puts("YES");
|
||
else
|
||
puts("NO");
|
||
}
|
||
return 0;
|
||
} |