星星灰暗着。

星星灰暗着。

你所见的的确是一个NOIp退役OIer的博客。

题解 P4363 【[九省联考2018]一双木棋chess】

posted on 2018-04-10 20:52:59 | under 题解 |

写了个比较通俗易懂的。

首先我们可以发现,存每个位置的状态显然是不行的。而作者又比较弱不会轮廓线上DP,所以只会写爆搜。
我们可以存储每一行放了多少个棋子,因为显而易见地,这些棋子都要放到最左边,所以可以很方便地表示一整个棋盘。
然后开始简易的对抗搜索,先手时取max,后手时取min,理解方法许多题解都有提到,不再赘述。
只需要每次判断在这一行下子是否可行,然后进行搜索即可。
因为直接暴力存储13进制数的原因,跑的比较慢,最大点0.1s。对于我这样的juruo来说可以了

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<tr1/unordered_map>
#define neko 12
#define chkmin(a,b) ((a)<(b)?(a):(b)) 
#define chkmax(a,b) ((a)>(b)?(a):(b))
#define f(i,a,b) for(register int i=(a);i<=(b);i=-(~i))
#define rf(i,a,b) for(register int i=(a);i>=(b);i=~(-i))
typedef long long ll;
int n,m,a[neko][neko],b[neko][neko],num[neko];
ll rdx=13;
std::tr1::unordered_map<ll,int>ht;
ll zip()//加密
{ll x=0;f(i,1,n)x=x*rdx+1ll*num[i];return x;}
void unzip(ll x)//解密
{rf(i,n,1)num[i]=x%rdx,x/=rdx;}
int dfs(ll now,bool hand)//hand=1 先手 =0 后手
{
    if(ht.count(now))return ht[now];
    unzip(now);int ans=hand?(-0x3f3f3f3f):(0x3f3f3f3f);ll aft;//注意初始值
    f(i,1,n)
    {
        if(num[i]<num[i-1])
        {
            ++num[i],aft=zip();
            if(hand)ans=chkmax(ans,dfs(aft,0)+a[i][num[i]]);
            else ans=chkmin(ans,dfs(aft,1)-b[i][num[i]]);
            --num[i];
        }
    }ht[now]=ans;
    return ans;
}
int main()
{
    scanf("%d%d",&n,&m);
    f(i,1,n)
     f(j,1,m)
      scanf("%d",&a[i][j]); 
    f(i,1,n)
     f(j,1,m)
      scanf("%d",&b[i][j]);
    f(i,0,n)num[i]=m;
    ht[zip()]=0;
    dfs(0,1);return printf("%d\n",ht[0]),0;//输出0状态的答案
}