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

传送门

对抗搜索都不会,我真是菜死了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;
}
上一篇:Mac_配置adb环境变量


下一篇:JS正则表达式的基础用法