状压dp POJ1185 炮兵阵地

题目链接：http://poj.org/problem?id=1185

和POJ3254一个套路：只是把“相邻”的定义改了一下

POJ3254：相邻指的是上下左右各一格

本题：相邻指的是上下左右各两格

同样地：数据还是很小，那么我们可以枚举前一行，以及前两行的状态来实现dp转移

dp[i][j][k]：前i行，第i行状态为k，第i-1行状态为j时放置炮兵数量的最大值

注意这里状态为j，指的是第j个合法状态，初始化的时候已经一一对应的枚举过了

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

int N,M;
char mp[110][20],num[110],tot;
int stk[70],cur[110];
int dp[110][70][70];

bool ok(int x){
	if (x&(x<<1)) return false;
	if (x&(x<<2)) return false;
	return true;
}

bool fit(int x,int k){
	if (cur[k] & x) return false;
	return true;
}

void init(){
	tot=0;
	int maxnum=1<<N;
	for(int i=0;i<maxnum;i++)
		if (ok(i))
			stk[++tot]=i;
}

int Count(int x){
	int cnt=0;
	while(x){
		cnt+=x%2;
		x/=2;
		//cnt++;
		//x&=(x-1);
	}
	return cnt;
}

int main(){
	while(scanf("%d%d",&M,&N)!=EOF){
		init();
		for(int i=1;i<=M;i++)
			scanf("%s",mp[i]+1);
		for(int i=1;i<=M;i++){
			cur[i]=0;
			for(int j=1;j<=N;j++)
				if (mp[i][j]=='H')
					cur[i]+=(1<<(j-1));
		}
		memset(dp,-1,sizeof(dp));
		for(int i=1;i<=tot;i++){
			num[i]=Count(stk[i]);
			if (fit(stk[i],1))
				dp[1][1][i]=num[i];
				//第0行为全空状态
				//第1行为当前枚举的合法状态
		}
		for(int i=2;i<=M;i++)
			for(int t=1;t<=tot;t++)
				if (fit(stk[t],i))
					for(int j=1;j<=tot;j++)
						if (!(stk[t] & stk[j]))
							for(int k=1;k<=tot;k++)
								if (!(stk[t] & stk[k]))
									if (dp[i-1][j][k] != -1)
										dp[i][k][t] = max(dp[i][k][t],dp[i-1][j][k]+num[t]);
		int ans=0;
		for(int i=1;i<=M;i++)
			for(int j=1;j<=tot;j++)
				for(int k=1;k<=tot;k++)
					ans=max(ans,dp[i][j][k]);
		printf("%d\n",ans);
	}
	return 0;
}