`
java-mans
  • 浏览: 11339603 次
文章分类
社区版块
存档分类
最新评论

POJ 2411 Mondriaan's Dream(DP---状态压缩)

 
阅读更多
/*

推荐:五星

动态规划、状态压缩、dfs

题意:m*n矩形,要求使用2*1的小块矩形进行填充,共存在多少种方法。

解题思路:使用1、0对每一格进行填充,首先考虑只有两行,则存在三种情况:竖着放置第i行为1,第i+1行为0;横着放置第i行为11,第i+1行为11;第i行正好为上一行竖着放置凸出来的部分,则第i行为0,所以下面一行肯定为1。使用d[i][s]表示第i行为状态s时的最大放置方法数。状态转移方程为:d[i][a]=sum(d[i-1][b]),其中a、b必须是一个合理的组合。根据a可以使用dfs查找出所有的b,题中使用vector数组进行存储。dfs()函数中用到三个递归:
dfs(col+1,(s1<<1) | 1,(s2<<1));//情况一
dfs(col+1,(s1<<1),(s2<<1) | 1);//情况三
dfs(col+2,(s1<<2) | 3,(s2<<2) | 3);//情况二

注意:①出为初始状态,表示正好被一个小矩形填充完,则加1
另外还有,题中需要在最后一行增加一行,并且第n+1行必须为1...1这样才能保证第n行无突出情况,具体实现是输出d[m+1][(1<<n)-1]的值。不过第0行必须为0...0来保证第1行都为1,具体实现为:d[0][]的赋值,如果为d[0][0],正好被一个小矩形填充完,加1,否则情况不存在+0,等于无效。其实这道题还是有点小迷糊,主要问题:d[0][]的赋值。
*/
//#define TEST
#include <cstdio>
#include <vector>
using namespace std;
const int nMax=13;
int m,n;
long long d[nMax][1<<nMax];
vector<int> v[1<<nMax];
void dfs(int col,int s1,int s2)
{
	if(col>=n)
	{
		if(s1<(1<<n) && s2<(1<<n))
			v[s2].push_back(s1);
		return;
	}
	dfs(col+1,(s1<<1) | 1,(s2<<1));
	dfs(col+1,(s1<<1),(s2<<1) | 1);
	dfs(col+2,(s1<<2) | 3,(s2<<2) | 3);
}
void dp()
{
	if(m<n) swap(m,n);
	for(int i=0;i<(1<<n);i++)
		v[i].clear();
	dfs(0,0,0);
	memset(d,0,sizeof(d));
	d[0][0]=1;//①
	int state=1<<n;
	for(int i=1;i<=m+1;i++)
		for(int s=0;s<state;s++)
		{
			for(int j=0;j<v[s].size();j++)
			{
				d[i][s]+=d[i-1][v[s][j]];
#ifdef TEST
			printf(":%d ",v[s][j]);
#endif
			}
#ifdef TEST
			printf("\n%d %d %lld\n",i,s,d[i][s]);
#endif
		}
}
int main()
{
	//freopen("f://data.in","r",stdin);
	while(scanf("%d %d",&m,&n)!=EOF)
	{
		if(m==0 && n==0) break;
		dp();
		printf("%lld\n",d[m+1][(1<<n)-1]);
	}
	return 0;
}


参考博客:http://www.cppblog.com/sdfond/archive/2009/07/31/91761.html


分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics