AcWing 1321. 取石子
原题链接
困难
作者:
lqmm1
,
2021-12-05 15:55:21
,
所有人可见
,
阅读 269
/*
看到这题后我才意思到博弈论原来如此的博大精深
博弈论的问题其实都可以用dp来写因为必胜态和必败态都可以递推没有环形依赖
博弈论里的sg函数其实也可以看成一个dp
所以博弈论的题目我们其实完全可以进行衍生为dp问题
复杂博弈论的题目我们有一种比较好用的解法
我们先思考一下这个题目简化版本怎么写然后再思考一下复杂的版本
在简化版本的基础上多加入点状态然后按sg函数的方式递推就可以完成了
这题我们可以先考虑每个堆的数都大于1的情况下我们先手的必胜和必败的情况
我们可以发现我们先手一定可以把堆数和石头总数的奇偶改变
所以我们假设b=堆数+石子的总个数-1
假设这个是奇数那么我们先手一定必胜反之先手一定必败
现在放开限制有a个堆石头个数是1
其他的堆加上对应石头的个数-1是b
这个时候我们去进行sg函数的方式搜索就可以解题了
*/
#include <iostream>
#include <cstring>
#include <algorithm>
#include<stdio.h>
#define int long long
using namespace std;
const int N = 100;
int f[55][50050];
int dp(int a,int b)
{
if(f[a][b]!=-1)return f[a][b];
if(!a)return f[a][b]=b%2;
if(b==1)return dp(a+1,0);
if(a&&!dp(a-1,b))return f[a][b]=1;
if(a>=2&&!dp(a-2,b+(b?3:2)))return f[a][b]=1;
if(b&&!dp(a,b-1))return f[a][b]=1;
if(b>=2&&!dp(a,b-1))return f[a][b]=1;
if(a&&b&&!dp(a-1,b+1))return f[a][b]=1;
return f[a][b]=0;
}
signed main()
{
int t;
cin >> t;
memset(f,-1,sizeof f);
while(t--)
{
int n;
cin >> n;
int a=0,b=0;
for(int i=1;i<=n;i++)
{
int x;
cin >> x;
if(x==1)a++;
else if(b==0)b+=x;
else b+=x+1;
}
if(dp(a,b)) cout << "YES"<<endl;
else cout << "NO"<<endl;
}
return 0;
}