洛谷P4363 一双木棋 chess
省选最水的一道题了。
且看我数个月AC一道题......
具体是这样的：
我们发现这个下了棋的地方一定形成一个锯齿形，那么怎么状态压缩呢？
维护轮廓线！
从左下角出发，向上为1，向右为0即可。
然后我们就开心的DP…等等
这按照什么顺序DP啊！！
好，那么我们退而求次，记忆化搜索！
然后就没有然后了…
需要注意的地方：
- 记得判断max还是min
- 二进制位运算一如既往的烦人
- DFS起点和终点的处理
- 求最大差值，转化为加A减B即可
那么我们调了一年后终于A了！！
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = ,INF = 0x7f7f7f7f;
int m,n,mp[<<],A[N][N],B[N][N],aim; bool who(int sta) { //判断该谁走的函数
int p=m,ans=;
while(sta) {
if(sta&) {
ans+=p;
}
else {
p--;
}
sta=sta>>;
}
return !(ans&);
} void out(int sta) { //输出这个状态(二进制)
int t[],T=;
fill(t,t+,);
while(sta) {
t[++T] = bool(sta&);
sta=sta>>;
}
printf(" ");
for(int i=m+n;i>=;i--) {
printf("%d",t[i]);
}
printf(" ");
return;
} int DFS(int now) { ///printf("DFS\n"); if(mp[now]) { // 记忆化
return mp[now];
}
if(now==aim) {
return ;
} bool f = who(now);
int p=,ans=(f?(-INF):INF);
for(int i=;i<m+n;i++) {
if(now&(<<i)) {
p++;
} // gay
if((!(now&(<<i)))&&(now&(<<(i+)))) { /* 10 */ /** 10 */ /// [p+1][m+p-i]
int nextsta = (now|(<<i))&(~(<<(i+)));
int x=p+;
int y=m+p-i;
if(f) {
ans=max(ans,DFS(nextsta)+A[x][y]);
}
else {
ans=min(ans,DFS(nextsta)-B[x][y]);
}
}
}
mp[now]=ans;
//printf("DFS:");
//out(now);
//printf("\n");
return ans;
} int main(){
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++) {
for(int j=;j<=m;j++) {
scanf("%d",&A[i][j]);
}
}
for(int i=;i<=n;i++) {
for(int j=;j<=m;j++) {
scanf("%d",&B[i][j]);
}
}
int s=; // 起点
for(int i=;i<=n;i++) {
aim=aim<<|; // 终点
s=s<<|;
}
for(int i=;i<=m;i++) {
s=s<<;
} printf("%d",DFS(s)); return ;
}
AC代码