【状压dp】[HDU1400 & poj2411] Mondriaan‘s Dream

对于棋盘上每个点，都有几种可能，1.不放  2.横放的前一个  3.横放的后一个  4.竖放的上一个  5.竖放的下一个

由于题目要求每个格子都被填满，所以可能1不存在

然后，我们可以考虑用1表示这个格子被放上了2/3/5这几种可能，然后通过二级制压缩状态

对于每一行都有一个数值来表示当前行的状态 now 以及上一行的状态 pre

我们可以通过dfs将所有的可能的两行之间的状态转移预处理出来

再填写第d列的时候 有这样几种可能

1.当前位置为可能2，那么就可以把下一个一起处理了，这时候要求上一行的两个位置也都为1

2.当前位置为可能4，这样要求上一行的d列的位置为1

3.当前位置可能为5，这样要求上一行的d列位置为0

 

然后再进行dp统计结果即可

 

代码

#include<bits/stdc++.h>
using namespace std;
int n,m,ca;
int state[200005][2];
long long dp[13][3005];
void dfs(int d,int now,int pre)
{
	if(d>m) return;
	if(d==m)
	{
		state[ca][0]=pre;
		state[ca++][1]=now;
		return;
	}
	dfs(d+1,(now<<1)|1,pre<<1);
	dfs(d+1,now<<1,(pre<<1)|1);
	dfs(d+2,(now<<2)|3,(pre<<2)|3);
}
int main()
{
	freopen("a.in","r",stdin);
	freopen("a.out","w",stdout);
	while(scanf("%d%d",&n,&m) && n)
	{
		//if(n<m) swap(n,m);
		ca=0;
		dfs(0,0,0);
		memset(dp,0,sizeof(dp));
		dp[0][(1<<m)-1]=1;
		for(int i=0;i<n;i++)
			for(int j=0;j<ca;j++)
				dp[i+1][state[j][1]]+=dp[i][state[j][0]];
		printf("%lld\n",dp[n][(1<<m)-1]);
	}
	return 0;
}

 

本文地址：https://blog.csdn.net/andyc_03/article/details/107609464