[搜索][博弈][模板] HDU 4597 Play Game

https://cn.vjudge.net/problem/HDU-4597

对抗搜索模板题。裸的minimax算法,搜索的时候注意max层要加上点的值,还没有仔细学α-β剪枝所以没用。。。 只用了记忆化(似乎也没什么卵用啊) 不过这个数据量,基础算法足够了。

 


#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
//#include

using namespace std;
typedef long long LL;
const int maxn=10000+5;
const int MOD=1e9+7;
const int INF=0x3f3f3f3f;

int card[2][maxn];
int vis[22][22][22][22][2];

int dfs(int ha,int ta,int hb,int tb,int m)//m==1 max , m==0 min
{

    if(vis[ha][ta][hb][tb][m]!=-1)
        return vis[ha][ta][hb][tb][m];
    if(ha>ta&&hb>tb)
        return vis[ha][ta][hb][tb][m]=0;
    int best;
    if(m)
    {
        best=-INF;
        if(ha<=ta)
        {
            best=max(best,card[0][ha]+dfs(ha+1,ta,hb,tb,0));
            best=max(best,card[0][ta]+dfs(ha,ta-1,hb,tb,0));
        }
        if(hb<=tb)
        {
            best=max(best,card[1][hb]+dfs(ha,ta,hb+1,tb,0));
            best=max(best,card[1][tb]+dfs(ha,ta,hb,tb-1,0));
        }
    }
    else
    {
        best=INF;
        if(ha<=ta)
        {
            best=min(best,dfs(ha+1,ta,hb,tb,1));
            best=min(best,dfs(ha,ta-1,hb,tb,1));
        }
        if(hb<=tb)
        {
            best=min(best,dfs(ha,ta,hb+1,tb,1));
            best=min(best,dfs(ha,ta,hb,tb-1,1));
        }
    }
    return vis[ha][ta][hb][tb][m]=best;
}

int main()
{
    int T,n;
    scanf("%d",&T);
    while(T--)
    {
        memset(vis,-1,sizeof(vis));
        scanf("%d",&n);
        for (int i=1;i<=n;++i)
            scanf("%d",&card[0][i]);
        for (int i=1;i<=n;i++)
            scanf("%d",&card[1][i]);
        int ans=dfs(1,n,1,n,1);
        printf("%d\n",ans);
    }
    return 0;
}



发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据