bzoj 3895 取石子 —— 博弈论

题目：https://www.lydsy.com/JudgeOnline/problem.php?id=3895

看了博客：https://blog.****.net/popoqqq/article/details/43989101

因为只是找有无必胜策略，所以可以搜索求解；

注意记忆化数组不必清空，因为同种状态对应的答案都一样。

代码如下：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int const maxm=;
int T,n,a[],f[][maxm];
bool v[][maxm];
bool dfs(int x,int y)
{
    if(v[x][y])return f[x][y]; v[x][y]=;
    if(!x)return f[x][y]=(y&);//
    if(y==)return f[x][y]=dfs(x+,);//既然v[x][y]=1,则必须赋f[x][y]
    if(x&&!dfs(x-,y))return f[x][y]=;
    if(x>&&!dfs(x-,y++(y!=)))return f[x][y]=;
    if(y&&!dfs(x,y-))return f[x][y]=;//
    if(x&&y&&!dfs(x-,y+))return f[x][y]=;//&&y
    return f[x][y]=;
}
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        int cnt=,st=;
        for(int i=;i<=n;i++)
        {
            scanf("%d",&a[i]);
            if(a[i]>)cnt++,st+=a[i];
        }
        st+=cnt-; cnt=n-cnt;
        if(st==-)st=;//!!!
//        memset(v,0,sizeof v);//不必清空！！！
        if(dfs(cnt,st))printf("YES\n");
        else printf("NO\n");
    }
    return ;
}