洛谷原題鏈接：P10975 Mondriaan's Dream
看數(shù)據(jù)范圍容易發(fā)現(xiàn)是狀壓DP
考慮如何規(guī)定狀態(tài)
設(shè)f(i,s)為第i行，填充格式為s的方案數(shù)，其中s為二進(jìn)制數(shù)，1表示在這個(gè)位置填充一個(gè)長(zhǎng)方形并使它延伸到i+1（即以i為起點(diǎn)的兩行一列的長(zhǎng)方形），0表示由i-1延伸而來(lái)或填充一個(gè)長(zhǎng)方形并使它不延伸到i+1（即在第i行放置一行兩列的長(zhǎng)方形）
轉(zhuǎn)移方程很簡(jiǎn)單，dp（i，s1）= dp(i-1, s2)+1,關(guān)鍵在于如何判斷 s1和s2是否合法

合法性判斷：

1. 如果i-1的第j位為1，代表j是一個(gè)延伸到i的長(zhǎng)方形，所以i的第j位就一定是由i-1的第j位填充的,即 s1 & s2 == 0
2. 對(duì)于s1，被s2填充延伸部分填充之后，不能存在一段連續(xù)奇數(shù)個(gè)0的序列（無(wú)法使用兩格的長(zhǎng)方形填充），即 s1 | s2 之后判斷

// x=s1 | s2;
// w=s1.size();
bool check(int x,int w) 
{
	bool flag=0;
	for(int j=0;j<w;j++)
	{
		if(!((1<<j) & x))
		{
			if(!flag) flag=1;
			else flag=0;
		}
		else if(flag) return 0;
	}
	if(flag) return 0; 
	return 1;
}

3. 考慮邊界的判斷，即當(dāng)i=n時(shí),s1只能等于0（無(wú)法向后面延伸）

代碼：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int const N=(1<<11);
int dp[12][N];
int n,m;

bool check(int x,int w)
{
	bool flag=0;
	for(int j=0;j<w;j++)
	{
		if(!((1<<j) & x))
		{
			if(!flag) flag=1;
			else flag=0;
		}
		else if(flag) return 0;
	}
	if(flag) return 0; 
	return 1;
}

int sovle (int h,int w)
{
	if(h==1)
	{
		if(w%2) return 0;
		else return 1;
	}
	int res=0;
	memset(dp,0,sizeof(dp));
	for(int i=0;i<(1<<w);i++) if(check(i,w)) dp[1][i]=1;
	
	for(int i=2;i<=h;i++)
	{
		for(int now=0;now<(1<<w);now++)
		{
			for(int bs=0;bs<(1<<w);bs++)
			{
				if(now & bs) continue;
				if(!check((now | bs),w)) continue;
				dp[i][now]+=dp[i-1][bs];
			}
			if(i==h) break;
		}
	}
	for(int i=0;i<(1<<w);i++) res+=dp[h][i];
	return res;
}

signed main(){
	cin>>n>>m;
	while(n or m)
	{
		cout<<sovle(n,m)<<endl;
		cin>>n>>m;
	}
	return 0;
}