取石子
Alice 和 Bob 两个好朋友又开始玩取石子了。
游戏开始时，有 NN 堆石子排成一排，然后他们轮流操作（Alice 先手），每次操作时从下面的规则中任选一个：
- 从某堆石子中取走一个；
- 合并任意两堆石子。
不能操作的人输。
Alice 想知道，她是否能有必胜策略。
输入格式
第一行输入 T，表示数据组数。
对于每组测试数据，第一行读入 N；
接下来 N 个正整数 a1,a2,⋯,aN ，表示每堆石子的数量。
输出格式
对于每组测试数据，输出一行。
输出 YES 表示 Alice 有必胜策略，输出 NO 表示 Alice 没有必胜策略。
数据范围
1≤T≤100,
1≤N≤50,
1≤ai≤1000
输入样例：
3
3
1 1 2
2
3 4
3
2 3 5
输出样例：
YES
NO
NO
代码
#include <cstdio>
#include <cstring>
#include<iostream>
using namespace std;
const int N = 55, M = 50050;
int f[N][M];
int dp(int a, int b)
{
int &v = f[a][b];
if (v != -1) return v;
// 简单情况
if (!a) return v = b % 2;
// 一般情况
// 上一次取完后 b中只有1堆 且只有1个石子 b=1+1-1=1 这堆并入a中
if (b == 1) return dp(a + 1, 0);
// 有a 从a中取1个
if (a && !dp(a - 1, b)) return v = 1;
// 有b 从b中取1个 or 合并b中2个
if (b && !dp(a, b - 1)) return v = 1;
// 合并a中2个
if (a >= 2 && !dp(a - 2, b + (b ? 3 : 2))) return v = 1;
// 合并a中1个b中1个
if (a && b && !dp(a - 1, b + 1)) return v = 1;
return v = 0;
}
int main()
{
memset(f, -1, sizeof f);
int T;
cin >> T;
while (T -- )
{
int n;
cin >> n;
int a = 0, b = 0;
for (int i = 0; i < n; i ++ )
{
int x;
cin >> x;
if (x == 1) a ++ ;
// b==0时 加1堆+加x石子=0 + 1+x-1=x
// b!=0时 加1堆+加x石子=原来的+x+1
else b += b ? x + 1 : x;
}
if (dp(a, b)) puts("YES");
else puts("NO");
}
return 0;
}