记录编号	387232	评测结果	AAAAAAAAAA
题目名称	[POJ1038]Bugs Integrated, Inc.	最终得分	100
用户昵称	Shirry	是否通过	通过
代码语言	C++	运行时间	4.934 s
提交时间	2017-03-26 11:50:27	内存使用	1.13 MiB

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
typedef long long LL;
int n,m;
int mp1[200][20]={0},mp2[200][20]={0};
int h;
LL f[2][59050]={0};
void dfs(int h,int p,int s1,int s2,int cnt){
	if(p>m+1)return;
	if(p==m+1){
		f[h&1][s1]=max(f[1-h&1][s2]+cnt,f[h&1][s1]);//滚动数组不用清空。会覆盖
		return;
	}
	if(mp1[h][p])dfs(h,p+3,s1*27+26,s2*27+13,cnt+1);//横放
	if(mp2[h][p])dfs(h,p+2,s1*9+8,s2*9,cnt+1);//竖放
	dfs(h,p+1,s1*3+1,s2*3+2,cnt);//当前行空，上一行满
	dfs(h,p+1,s1*3,s2*3+1,cnt);//当前行和上一行都为空
	dfs(h,p+1,s1*3+2,s2*3+2,cnt);//虚放骨牌 以便无空隙的放骨牌 最后的目标状态就很明确了
}
int work(){
	freopen("exameight.in","r",stdin);
	freopen("exameight.out","w",stdout);
	int T;
	scanf("%d",&T);
	for(int i=1;i<=T;i++){
		memset(mp1,1,sizeof(mp1));
		memset(mp2,1,sizeof(mp2));
		memset(f,0,sizeof(f));
		int k;
		scanf("%d%d%d",&n,&m,&k);
		int a,b;
		for(int j=1;j<=k;j++){
			scanf("%d%d",&a,&b);
			for(int p=0;p<2;p++){
				for(int q=0;q<3;q++){//以(a,b)为左上角。因为我们是从右下角开始放骨牌
					if(b-q>=0)mp1[a+p][b-q]=0;
					if(b-p>=0)mp2[a+q][b-p]=0;
				}
			}
		}
		memset(mp2[2],0,sizeof(mp2[2]));//若从右下角开始向上竖放骨牌。会到-1行
		for(h=2;h<=n;h++)dfs(h,1,0,0,0);//because mpx[h][p]...p should start as 1  表示该放
		int goal=pow(3.0,(double)m)-1;
		printf("%lld\n",f[n&1][goal]);
	}
	return 0;
}
int Sh=work();
int main(){
	return 0;
}