传送门

对抗搜索都不会,我真是菜死了qwq

首先根据题目条件,可以发现从上到下每一行的棋子数是单调不增的,然后n m都比较小,如果把状态搜出来,可以发现合法状态并不多,所以可以用一个11进制数表示状态,然后对应的值存在map里.然后状态之间的转移就看这个状态应该是谁下,如果是先手就取max,否则取min转移

// luogu-judger-enable-o2

#include<bits/stdc++.h>

#define LL long long

#define il inline

using namespace std;

const int N=1e5+100;

il int rd()

{

    int x=0,w=1;char ch=0;

    while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}

    while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}

    return x*w;

}

map<LL,int> f;

LL ma,pw[11];

int n,m,a[11][11],b[11][11];

int sov(LL o)

{

    if(o==ma) return 0;

    if(f.find(o)!=f.end()) return f[o];

    int c[11],op=0;

    c[0]=-1;

    LL oo=o;

    for(int i=1;i<=n;++i)

        c[i]=oo%11,op^=c[i]&1,oo/=11;

    f[o]=1<<30;

    if(!op) f[o]=-f[o];

    for(int i=1;i<=n;++i)

        if(c[i]<m&&c[i]!=c[i-1])

        {

            LL nxt=o+pw[i-1];

            op?f[o]=min(f[o],sov(nxt)-b[i][c[i]+1]):f[o]=max(f[o],sov(nxt)+a[i][c[i]+1]);

        }

    return f[o];

}

int main()

{

    pw[0]=1;

    for(int i=1;i<=10;++i) pw[i]=pw[i-1]*11;

    n=rd(),m=rd();

    for(int i=1;i<=n;++i)

        for(int j=1;j<=m;++j)

            a[i][j]=rd();

    for(int i=1;i<=n;++i)

        for(int j=1;j<=m;++j)

            b[i][j]=rd();

    for(int i=0;i<n;++i) ma+=pw[i];

    ma*=m;

    printf("%d\n",sov(0));

    return 0;

}