[九省联考2018]一双木棋chess——搜索+哈希

亦凉 2021-09-29 13:42 183阅读 0赞

题目：bzoj5248 [https://www.lydsy.com/JudgeOnline/problem.php?id=5248][https_www.lydsy.com_JudgeOnline_problem.php_id_5248]

洛谷P4363 [https://www.luogu.org/problemnew/show/P4363][https_www.luogu.org_problemnew_show_P4363]

终于A了(虽然得开O2才能过)！

其实就是暴搜，用一个 n+1 进制数表示状态，进行最优策略转移即可；

注意 cnt\[\] 如果开成全局变量就不能每次翻译那个 n+1 进制数，否则会影响其它层的搜索；

(还有一种神奇的状态压缩是有几个用了 k 个1的列，就在第 k 个0后面加几个1……)

代码如下：

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<map>
    using namespace std;
    typedef long long ll;
    map<ll,ll>mp;
    map<ll,bool>vis;
    int n,m,s[3][15][15],inf=1e9,cnt[15];
    ll pw(int a,int b)
    {
        ll ret=1;
        while(b){
        if(b&1)ret*=a;a*=a;b>>=1;}
        return ret;
    }
    ll dfs(ll x,bool f)
    {
        if(vis[x])return mp[x];
        vis[x]=1;mp[x]=-inf;ll tx=x;
    //    for(int i=m;i;i--)cnt[i]=tx%(n+1),tx/=(n+1);
        if(cnt[m]==n)return mp[x]=0;
        for(int i=1;i<=m;i++)
        {
            if(cnt[i]==n||(i>1&&cnt[i-1]<=cnt[i]))continue;
            cnt[i]++;
            ll y=x+pw(n+1,m-i);
            mp[x]=max(mp[x],s[f][cnt[i]][i]-dfs(y,!f));
            cnt[i]--;
        }
        return mp[x];
    }
    int main()
    {
        scanf("%d%d",&n,&m);
        for(int k=0;k<=1;k++)
            for(int i=1;i<=n;i++)
                for(int j=1;j<=m;j++)
                    scanf("%d",&s[k][i][j]);
        printf("%lld",dfs(0,0));
    }

转载于:https://www.cnblogs.com/Zinn/p/9164001.html

[https_www.lydsy.com_JudgeOnline_problem.php_id_5248]: https://www.lydsy.com/JudgeOnline/problem.php?id=5248
[https_www.luogu.org_problemnew_show_P4363]: https://www.luogu.org/problemnew/show/P4363