POJ 2411 Mondriaan's Dream 【状压Dp】 By cellur925

这道题暑假做的时候太模糊了，以前的那篇题解大家就别看了==。今天再复习状压感觉自己当时在写些什么鸭...。

题目大意：给你一个\(n\)*\(m\)的棋盘和许多\(1*2\)的骨牌，骨牌可以竖放或横放，问有多少种方案将骨牌铺满。

设计状态，\(f[i][j]\)表示当前在第\(i\)行，之前的所有行都已经铺满，当前行的状态为\(j\)的方案数。如果我们对01串的定义仍确定为1为放了0为没放，那么真的对嘛？

好像不行，存出不了那么多信息。我们试着改变0和1的含义。因为骨牌要么是横放要么是竖放，那么我们设第\(k\)位为1是一个竖矩形的上面一半，为0代表其他情况。

考虑转移，第\(i-1\)行能转移到第\(i\)行当且仅当①这一行状态与上一行状态与运算为0.（保证了每个数字为1的位下面一定为0，以继续补全）。②两行状态或运算后的二进制表示，连续的0长度必须为偶数，表示横放。

于是我们可以预处理出所有横放的情况，再进行\(O(4^m*n)\)的转移。目标状态\(f[n][0]\)。

把01的含义改变的思想妙啊。

#include<cstdio>

#include<algorithm>

#include<cstring>

using namespace std;

typedef long long ll;

int n,m,fake;

ll f[12][4200000];

bool qwq[4200000];

int main()

{

	while(scanf("%d%d",&n,&m)!=EOF&&n!=0)

	{

		fake=(1<<m)-1;

//		for(int i=0;i<=fake;i++)

//			if(check(i)) qwq[i]=1;

		for(int i=0;i<=fake;i++)

		{

			bool cnt=0,has_odd=0;

			for(int j=0;j<m;j++)

				if((i>>j)&1) has_odd|=cnt,cnt=0;

				else cnt^=1;

			qwq[i]=has_odd | cnt ? 0 : 1;

		}

    	f[0][0]=1;

    	for(int i=1;i<=n;i++)

    		for(int j=0;j<=fake;j++)

    		{

    			f[i][j]=0;

    			for(int k=0;k<=fake;k++)

    			{

    				if(j&k) continue;

    				if(!qwq[j|k]) continue;

    				f[i][j]+=f[i-1][k];

				}

			}

		printf("%lld\n",f[n][0]);

	}

	return 0;

}

巴特西

POJ 2411 Mondriaan's Dream 【状压Dp】 By cellur925

最新文章

热门文章