[九省联考 2018] 一双木棋

思路

WC 试机题,没想到居然能做出来QwQ

放过棋子的部分一定是一个阶梯形的,我们试图用状压表示一下这个形状,可以想出一种简单的方案,用一个$n+m$位的二进制数,如果一位是$1$就表示这一段轮廓线是水平的,否则就是竖直的。设$f_{S}$表示当前放过棋子的部分的形状是$S$,剩下的部分放置的最优结果,那么直接记搜一下就可以了

代码

#include <iostream>
#include <cstdio>

template <typename T> void in(T &_){
	char c=getchar(); int fl=1; _=0;
	while(c<'0'||c>'9') fl=c=='-'?-1:fl, c=getchar();
	while(c>='0'&&c<='9') _=_*10+c-'0', c=getchar(); _*=fl;
}

int N, M, A[15][15], B[15][15], ans[1<<20];
bool vis[1<<20];

void print(int sta){
	for(int i=0; i<N+M; i++) putchar('0'+((sta>>i)&1));
}

int dfs(int sta, int opt){
	if(vis[sta]) return ans[sta];
	int res, orz;
	if(opt){						
		res=-0x3f3f3f3f, orz=0x3f3f3f3f;
		for(int i=0; i<N+M-1; i++) if(!((sta>>i)&1) && ((sta>>(i+1))&1)){
			int tmp=dfs(sta^(1<<i)^(1<<(i+1)), opt^1), x=N, y=1;
			for(int j=0; j<i; j++) if((sta>>j)&1) y++; else x--;
			res=std::max(res, tmp+A[x][y]);
		}
	}else{
		res=0x3f3f3f3f, orz=-0x3f3f3f3f;
		for(int i=0; i<N+M-1; i++) if(!((sta>>i)&1) && ((sta>>(i+1))&1)){
			int tmp=dfs(sta^(1<<i)^(1<<(i+1)), opt^1), x=N, y=1;
			for(int j=0; j<i; j++) if((sta>>j)&1) y++; else x--;
			res=std::min(res, tmp-B[x][y]);
		}
	}
	vis[sta]=true; ans[sta]=res; return res;
}

int main(){
	in(N); in(M);
	for(int i=1; i<=N; i++) for(int j=1; j<=M; j++) in(A[i][j]);
	for(int i=1; i<=N; i++) for(int j=1; j<=M; j++) in(B[i][j]);
	int sta=(1<<M)-1; vis[sta]=true;
	printf("%d\n", dfs(((1<<M)-1)<<N, 1));
	return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注