[九省联考2018]一双木棋chess

题目

由于每一行都要从左开始并且保证了每一行不超过上一行，所以不难发现状态数很少，搜一发只有35w左右

于是状压每一行取到了第几个数，可以用一个\(m+1\)进制数表示，之后记搜就赢了

代码，里面那个hash_table是手写哈希表被卡的惨痛经历的证明

#include<tr1/unordered_map>
#include<bits/stdc++.h>
#define re register
#define LL long long
const int inf=1e8;
const int maxn=402717;
using namespace std::tr1;
int a[2][11][11],vis[2][maxn],dp[2][maxn],n,m;
LL pw[11],S;
inline int max(int a,int b) {return a>b?a:b;}
inline int min(int a,int b) {return a<b?a:b;}
struct Hash_table {
    int cnt;unordered_map<LL,int> ma;
    inline int ins(LL x) {return ma[x]=++cnt;}
    inline int fid(LL x) {return ma[x];}
}Hash;
int dfs(int o,LL state) {
    if(state==S) return 0;
    int k=Hash.fid(state);
    if(vis[o][k]) return dp[o][k];
    if(!k) k=Hash.ins(state);
    vis[o][k]=1;
    if(!o) {
        int nw=-inf,pre=m;
        for(re int i=1;i<=n;i++) {
            LL d=state/pw[n-i];d%=(m+1);
            if(d<pre&&d<m) nw=max(nw,dfs(o^1,state+pw[n-i])+a[0][i][d+1]);
            pre=d;
        }
        return dp[o][k]=nw;
    }
    if(o) {
        int nw=inf,pre=m;
        for(re int i=1;i<=n;i++) {
            LL d=state/pw[n-i];d%=(m+1);
            if(d<pre&&d<m) nw=min(nw,dfs(o^1,state+pw[n-i])-a[1][i][d+1]);
            pre=d;
        }
        return dp[o][k]=nw;
    }
}
int main() {
    scanf("%d%d",&n,&m);
    pw[0]=1;for(re int i=1;i<=n;i++) pw[i]=1ll*pw[i-1]*(m+1);
    for(re int i=1;i<=n;i++) S=1ll*S*(m+1),S+=m;
    for(re int i=1;i<=n;i++)
        for(re int j=1;j<=m;j++) scanf("%d",&a[0][i][j]);
    for(re int i=1;i<=n;i++)
        for(re int j=1;j<=m;j++) scanf("%d",&a[1][i][j]);
    return printf("%d\n",dfs(0,0)),0;
}//g++ lg4636.cpp -o lg4636

[九省联考2018]一双木棋chess

原文：https://www.cnblogs.com/asuldb/p/12104526.html