「Luogu4363/BZOJ5248」[九省联考2018]一双木棋chess
学校省选模拟居然拿九省联考来考
然而我还是(toospace young)，搞不懂什么叫最优
让二者的答案最接近可以拿到(25)分的好成绩
Solution
首先可以知道菲菲想要最大化(ans=Ansa-Ansb)，牛牛想要最小化
那么我们可以用对抗搜索大力爆搜
可以拿到50分
#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long ll;
template <typename T> void read(T &t)
{
t=0;int f=0;char c=getchar();
while(!isdigit(c)){f|=c=='-';c=getchar();}
while(isdigit(c)){t=t*10+c-'0';c=getchar();}
if(f)t=-t;
}
const int maxn=15,maxm=15;
int n,m;
int A[maxn][maxm],B[maxn][maxm];
int ocr[maxn][maxm];
int dfs(int step)
{
if(step==n*m+1)
return 0;
int re=0;
if(step&1)re=-0x3f3f3f3f;
else re=0x3f3f3f3f;
for(register int i=1;i<=n;++i)
for(register int j=1;j<=m;++j)
if(!ocr[i][j] && ocr[i-1][j] && ocr[i][j-1])
{
ocr[i][j]=1;
if(step&1)re=max(re,dfs(step+1)+A[i][j]);
else re=min(re,dfs(step+1)-B[i][j]);
ocr[i][j]=0;
}
return re;
}
int main()
{
read(n);read(m);
for(register int i=1;i<=n;++i)
for(register int j=1;j<=m;++j)
read(A[i][j]);
for(register int i=1;i<=n;++i)
for(register int j=1;j<=m;++j)
read(B[i][j]);
for(register int i=0;i<=n;++i)ocr[i][0]=1;
for(register int i=0;i<=m;++i)ocr[0][i]=1;
printf("%d",dfs(1));
return 0;
}
显然这个东西可以记忆化一下
用(map)存一下棋盘的哈希值，吸氧的情况下是能A掉的
#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <map>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
template <typename T> void read(T &t)
{
t=0;int f=0;char c=getchar();
while(!isdigit(c)){f|=c=='-';c=getchar();}
while(isdigit(c)){t=t*10+c-'0';c=getchar();}
if(f)t=-t;
}
const int maxn=15,maxm=15;
int n,m;
int A[maxn][maxm],B[maxn][maxm];
int ocr[maxn][maxm];
map<ull,int> rec;
ull Hash()
{
ull re=0;
for(register int i=1;i<=n;++i)
for(register int j=1;j<=m;++j)
re=re*3ull+ocr[i][j];
return re;
}
int dfs(int step)
{
if(step==n*m+1)
return 0;
int re=0;
ull h=Hash();
if(rec.find(h)!=rec.end())
return rec[h];
if(step&1)re=-0x3f3f3f3f;
else re=0x3f3f3f3f;
for(register int i=1;i<=n;++i)
for(register int j=1;j<=m;++j)
if(!ocr[i][j] && ocr[i-1][j] && ocr[i][j-1])
{
ocr[i][j]=1;
if(step&1)re=max(re,dfs(step+1)+A[i][j]);
else re=min(re,dfs(step+1)-B[i][j]);
ocr[i][j]=0;
}
return rec[h]=re;
}
int main()
{
read(n);read(m);
for(register int i=1;i<=n;++i)
for(register int j=1;j<=m;++j)
read(A[i][j]);
for(register int i=1;i<=n;++i)
for(register int j=1;j<=m;++j)
read(B[i][j]);
for(register int i=0;i<=n;++i)ocr[i][0]=1;
for(register int i=0;i<=m;++i)ocr[0][i]=1;
printf("%d",dfs(1));
return 0;
}
经过百度一下之后，发现此类对抗搜索还有一种优化，叫做(Alpha-Beta)优化
在此仅放上介绍链接，不再赘述
对于此题，我们如果使用(Alpha-Beta)优化，也能获得70分的成绩
#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
template <typename T> void read(T &t)
{
t=0;int f=0;char c=getchar();
while(!isdigit(c)){f|=c=='-';c=getchar();}
while(isdigit(c)){t=t*10+c-'0';c=getchar();}
if(f)t=-t;
}
const int maxn=15,maxm=15;
int n,m;
int A[maxn][maxm],B[maxn][maxm];
int ocr[maxn][maxm];
const int inf=0x3f3f3f3f;
int dfs(int step,int alpha,int beta,int nowa,int nowb)
{
if(step==n*m+1)
return nowa-nowb;
if(step&1)
{
for(register int i=1;i<=n;++i)
for(register int j=1;j<=m;++j)
if(!ocr[i][j] && ocr[i-1][j] && ocr[i][j-1])
{
ocr[i][j]=1;
alpha=max(alpha,dfs(step+1,alpha,beta,nowa+A[i][j],nowb));
ocr[i][j]=0;
if(alpha>=beta)return alpha;
}
return alpha;
}
else
{
for(register int i=1;i<=n;++i)
for(register int j=1;j<=m;++j)
if(!ocr[i][j] && ocr[i-1][j] && ocr[i][j-1])
{
ocr[i][j]=1;
beta=min(beta,dfs(step+1,alpha,beta,nowa,nowb+B[i][j]));
ocr[i][j]=0;
if(alpha>=beta)return beta;
}
return beta;
}
}
int main()
{
read(n);read(m);
for(register int i=1;i<=n;++i)
for(register int j=1;j<=m;++j)
read(A[i][j]);
for(register int i=1;i<=n;++i)
for(register int j=1;j<=m;++j)
read(B[i][j]);
for(register int i=0;i<=n;++i)ocr[i][0]=1;
for(register int i=0;i<=m;++i)ocr[0][i]=1;
printf("%d",dfs(1,-inf,inf,0,0));
return 0;
}