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

· · 题解

显然放下的棋子构成一个阶梯型。

我们爆搜一发状态量，发现只有35万多种，这不随便做？

然后在用map记录答案的情况下一发min-max对抗搜索就好了。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#define debug cout
typedef long long int lli;
using namespace std;
const int maxn=15,base=12;
const int inf=0x3f3f3f3f;

map<lli,int> mp;
int a[maxn][maxn],b[maxn][maxn];
int hei[maxn]; // hei[0] = n .
int n,m;

inline lli hsh() {
    lli ret = 0;
    for(int i=1;i<=n;i++) ret = ret * base + hei[i];
    return ret;
}
inline void unzip(lli t) {
    for(int i=n;i;i--) hei[i] = t % base , t /= base;
}
inline int getnxt() {
    int ret = 0;
    for(int i=1;i<=n;i++) ret += hei[i];
    return ret & 1; // 0 means max , 1 means min .
}
inline int dfs(lli sta) {
    if( mp.find(sta) != mp.end() ) return mp[sta];
    unzip(sta);
    int tpe = getnxt() , ret = tpe ? inf : -inf;
    for(int i=1;i<=n;i++)
        if( hei[i-1] > hei[i] ) {
            ++hei[i];
            lli h = hsh();
            if( !tpe ) ret = max( ret , dfs(h) + a[i][hei[i]] );
            else ret = min( ret , dfs(h) - b[i][hei[i]] );
            --hei[i];
        }
    return mp[sta] = ret;
}

int main() {
    scanf("%d%d",&n,&m) , hei[0] = m;
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",a[i]+j);
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",b[i]+j);
    for(int i=1;i<=n;i++) hei[i] = m;
    lli full = hsh(); mp[full] = 0;
    dfs(0);
    printf("%d\n",mp[0]);
    return 0;
}