「Luogu4363/BZOJ5248」[九省联考2018]一双木棋chess

川长思鸟来 2022-01-05 12:17 133阅读 0赞

# 「Luogu4363/BZOJ5248」\[九省联考2018\]一双木棋chess #

学校省选模拟居然拿九省联考来考

然而我还是\\(too\\space young\\)，搞不懂什么叫最优

让二者的答案最接近可以拿到\\(25\\)分的好成绩

--------------------

[problem][]

# Solution #

首先可以知道菲菲想要最大化\\(ans=Ansa-Ansb\\)，牛牛想要最小化

那么我们可以用对抗搜索大力爆搜

可以拿到50分

#include <cstdio>
    #include <iostream>
    #include <cstdlib>
    #include <cstring>
    #include <cmath>
    #include <algorithm>
    using namespace std;
    typedef long long ll;
    
    template <typename T> void read(T &t)
    {
        t=0;int f=0;char c=getchar();
        while(!isdigit(c)){f|=c=='-';c=getchar();}
        while(isdigit(c)){t=t*10+c-'0';c=getchar();}
        if(f)t=-t;
    }
    
    const int maxn=15,maxm=15;
    int n,m;
    int A[maxn][maxm],B[maxn][maxm];
    int ocr[maxn][maxm];
    
    int dfs(int step)
    {
        if(step==n*m+1)
            return 0;
        int re=0;
        if(step&1)re=-0x3f3f3f3f;
        else re=0x3f3f3f3f;
        for(register int i=1;i<=n;++i)
            for(register int j=1;j<=m;++j)
                if(!ocr[i][j] && ocr[i-1][j] && ocr[i][j-1])
                {
                    ocr[i][j]=1;
                    if(step&1)re=max(re,dfs(step+1)+A[i][j]);
                    else re=min(re,dfs(step+1)-B[i][j]);
                    ocr[i][j]=0;
                }
        return re;
    }
    
    int main()
    {
        read(n);read(m);
        for(register int i=1;i<=n;++i)
            for(register int j=1;j<=m;++j)
                read(A[i][j]);
        for(register int i=1;i<=n;++i)
            for(register int j=1;j<=m;++j)
                read(B[i][j]);
        for(register int i=0;i<=n;++i)ocr[i][0]=1;
        for(register int i=0;i<=m;++i)ocr[0][i]=1;
        printf("%d",dfs(1));
        return 0;
    }

显然这个东西可以记忆化一下

用\\(map\\)存一下棋盘的哈希值，吸氧的情况下是能A掉的

#include <cstdio>
    #include <iostream>
    #include <cstdlib>
    #include <cstring>
    #include <cmath>
    #include <algorithm>
    #include <map>
    using namespace std;
    typedef long long ll;
    typedef unsigned long long ull;
    
    template <typename T> void read(T &t)
    {
        t=0;int f=0;char c=getchar();
        while(!isdigit(c)){f|=c=='-';c=getchar();}
        while(isdigit(c)){t=t*10+c-'0';c=getchar();}
        if(f)t=-t;
    }
    
    const int maxn=15,maxm=15;
    
    int n,m;
    int A[maxn][maxm],B[maxn][maxm];
    int ocr[maxn][maxm];
    map<ull,int> rec;
    
    ull Hash()
    {
        ull re=0;
        for(register int i=1;i<=n;++i)
            for(register int j=1;j<=m;++j)
                re=re*3ull+ocr[i][j];
        return re;
    }
    
    int dfs(int step)
    {
        if(step==n*m+1)
            return 0;
        int re=0;
        ull h=Hash();
        if(rec.find(h)!=rec.end())
            return rec[h];
        if(step&1)re=-0x3f3f3f3f;
        else re=0x3f3f3f3f;
        for(register int i=1;i<=n;++i)
            for(register int j=1;j<=m;++j)
                if(!ocr[i][j] && ocr[i-1][j] && ocr[i][j-1])
                {
                    ocr[i][j]=1;
                    if(step&1)re=max(re,dfs(step+1)+A[i][j]);
                    else re=min(re,dfs(step+1)-B[i][j]);
                    ocr[i][j]=0;
                }
        return rec[h]=re;
    }
    
    int main()
    {
        read(n);read(m);
        for(register int i=1;i<=n;++i)
            for(register int j=1;j<=m;++j)
                read(A[i][j]);
        for(register int i=1;i<=n;++i)
            for(register int j=1;j<=m;++j)
                read(B[i][j]);
        for(register int i=0;i<=n;++i)ocr[i][0]=1;
        for(register int i=0;i<=m;++i)ocr[0][i]=1;
        printf("%d",dfs(1));
        return 0;
    }

--------------------

经过百度一下之后，发现此类对抗搜索还有一种优化，叫做\\(Alpha-Beta\\)优化

在此仅放上[介绍链接][Link 1]，不再赘述

对于此题，我们如果使用\\(Alpha-Beta\\)优化，也能获得70分的成绩

#include <cstdio>
    #include <iostream>
    #include <cstdlib>
    #include <cstring>
    #include <cmath>
    #include <algorithm>
    using namespace std;
    typedef long long ll;
    typedef unsigned long long ull;
    
    template <typename T> void read(T &t)
    {
        t=0;int f=0;char c=getchar();
        while(!isdigit(c)){f|=c=='-';c=getchar();}
        while(isdigit(c)){t=t*10+c-'0';c=getchar();}
        if(f)t=-t;
    }
    
    const int maxn=15,maxm=15;
    
    int n,m;
    int A[maxn][maxm],B[maxn][maxm];
    int ocr[maxn][maxm];
    
    const int inf=0x3f3f3f3f;
    
    
    int dfs(int step,int alpha,int beta,int nowa,int nowb)
    {
        if(step==n*m+1)
            return nowa-nowb;
        if(step&1)
        {
            for(register int i=1;i<=n;++i)
                for(register int j=1;j<=m;++j)
                    if(!ocr[i][j] && ocr[i-1][j] && ocr[i][j-1])
                    {
                        ocr[i][j]=1;
                        alpha=max(alpha,dfs(step+1,alpha,beta,nowa+A[i][j],nowb));
                        ocr[i][j]=0;
                        if(alpha>=beta)return alpha;
                    }
            return alpha;
        }
        else
        {
            for(register int i=1;i<=n;++i)
                for(register int j=1;j<=m;++j)
                    if(!ocr[i][j] && ocr[i-1][j] && ocr[i][j-1])
                    {
                        ocr[i][j]=1;
                        beta=min(beta,dfs(step+1,alpha,beta,nowa,nowb+B[i][j]));
                        ocr[i][j]=0;
                        if(alpha>=beta)return beta;
                    }
            return beta;
        }
    }
    
    int main()
    {
        read(n);read(m);
        for(register int i=1;i<=n;++i)
            for(register int j=1;j<=m;++j)
                read(A[i][j]);
        for(register int i=1;i<=n;++i)
            for(register int j=1;j<=m;++j)
                read(B[i][j]);
        for(register int i=0;i<=n;++i)ocr[i][0]=1;
        for(register int i=0;i<=m;++i)ocr[0][i]=1;
        printf("%d",dfs(1,-inf,inf,0,0));
        return 0;
    }

转载于:https://www.cnblogs.com/lizbaka/p/10520853.html

[problem]: https://www.luogu.org/problemnew/show/P4363
[Link 1]: https://blog.csdn.net/chenxiaoran666/article/details/82809890