博弈论-----取石子
Alice 和 Bob 两个好朋友又开始玩取石子了。
游戏开始时，有 NN 堆石子排成一排，然后他们轮流操作（Alice 先手），每次操作时从下面的规则中任选一个：
从某堆石子中取走一个；
合并任意两堆石子。
不能操作的人输。
Alice 想知道，她是否能有必胜策略。
输入格式
第一行输入 TT，表示数据组数。
对于每组测试数据，第一行读入 NN；
接下来 NN 个正整数 a1,a2,⋯,aNa1,a2,⋯,aN ，表示每堆石子的数量。
输出格式
对于每组测试数据，输出一行。
输出 YES 表示 Alice 有必胜策略，输出 NO 表示 Alice 没有必胜策略。
数据范围
1≤T≤1001≤T≤100,
1≤N≤501≤N≤50,
1≤ai≤10001≤ai≤1000
输入样例：
3
3
1 1 2
2
3 4
3
2 3 5
输出样例：
YES
NO
NO
#include
#include
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 b % 2;
if (b == 1) return dp(a + 1, 0);
if (a && !dp(a - 1, b)) return v = 1;
if (b && !dp(a, b - 1)) return v = 1;
if (a >= 2 && !dp(a - 2, b + (b ? 3 : 2))) return v = 1;
if (a && b && !dp(a - 1, b + 1)) return v = 1;
return v = 0;
}
int main(){
memset(f, -1, sizeof f);
int T;
scanf("%d", &T);
while(T --){
int n;
scanf("%d", &n);
int a = 0, b = 0;
for (int i = 0; i < n ; i ++){
int x;
scanf("%d", &x);
if(x == 1) a ++;
else b += (b ? x + 1 : x);
}
if (dp(a, b)) puts("YES");
else puts("NO");
}
return 0;
}
作者：王文波～
