本文是講解狀態(tài)壓縮DP的第二部分，仍然是對(duì)基于連通性問(wèn)題的探討與學(xué)習(xí)。一些概念性的問(wèn)題，以及基本解法 在第一節(jié)中講過(guò)，這里就不再贅述。

對(duì)典例蒙德里安的夢(mèng)想的分析直接看例題：

求把 N×M 的棋盤(pán)分割成若干個(gè) 1×2 的長(zhǎng)方形，有多少種方案。

例如當(dāng) N=2，M=4 時(shí)，共有 5 種方案。當(dāng) N=2，M=3 時(shí)，共有 3 種方案。

如下圖所示：

輸入格式

輸入包含多組測(cè)試用例。

每組測(cè)試用例占一行，包含兩個(gè)整數(shù) N 和 M。

當(dāng)輸入用例 N=0，M=0 時(shí)，表示輸入終止，且該用例無(wú)需處理。

輸出格式

每個(gè)測(cè)試用例輸出一個(gè)結(jié)果，每個(gè)結(jié)果占一行。

數(shù)據(jù)范圍

1≤N,M≤11

輸入樣例：

1 2
1 3
1 4
2 2
2 3
2 4
2 11
4 11
0 0

輸出樣例：

1
0
1
2
3
5
144
51205

算法分析:

1. 拿到題目，我們先從暴力的角度思考，如果我們暴力枚舉每一個(gè)格子，那么時(shí)間復(fù)雜度為2^121, 是會(huì)超時(shí)的，因此考慮用記憶化搜索來(lái)優(yōu)化， 于是我們用動(dòng)態(tài)規(guī)劃來(lái)考慮這個(gè)問(wèn)題。

2. 性質(zhì)挖掘：同時(shí)，這里我們可以發(fā)現(xiàn)一個(gè)性質(zhì)：先將所有橫著的小方塊擺滿(mǎn)再放豎著的小方塊，方案數(shù)和總方案數(shù)是相等的，因?yàn)楫?dāng)所有橫著的合法小方塊放完后，豎著的小方塊只需往空里塞即可，這一點(diǎn)可以從樣例觀(guān)察到。

即核心：先放橫著的，再放豎著的。

3. 若我們按列枚舉放小方塊，可以發(fā)現(xiàn)，

（1）在第i列放橫著小方塊的方案會(huì)受到第i - 1列的影響；

（2）并且若在同一個(gè)狀態(tài)i中，上一個(gè)小方塊和下一個(gè)小方塊之間的空格數(shù)為奇數(shù)時(shí)是不合法的（因?yàn)榭崭駭?shù)奇數(shù)個(gè)時(shí)無(wú)法用豎著的小方格塞滿(mǎn)棋盤(pán)，會(huì)留下空缺）

第一種情況，如下圖：

若兩個(gè)方塊重疊時(shí)則該方案是不合法的（圖中為合法情況），

這里我們?cè)O(shè)第i - 1列的方塊的擺放方案狀態(tài)為 k，第 i 列方塊的擺放方案為 j。

第二種情況：

第一種方案是不合法的，因?yàn)樵跔顟B(tài) j 和狀態(tài)k，中間的空格數(shù)為奇數(shù)，不能放下豎著的(1 x 2)小方塊

第二種方案則是合法的 :

4. 接下來(lái)，我們思考動(dòng)態(tài)規(guī)劃的一般流程：狀態(tài)表示，以及狀態(tài)計(jì)算，首先是狀態(tài)表示根據(jù)前文的分析，我們這里需要維護(hù)的變量只有三個(gè)：

①當(dāng)前在哪一列，②當(dāng)前列的狀態(tài)是什么，③當(dāng)前狀態(tài)方案數(shù)。

所以我們可以定義狀態(tài)表示為f[i][j]

狀態(tài)表示: f[i][j] 表示已經(jīng)將前i - 1列擺好，且從第 i - 1 列伸出到第i 列的狀態(tài)為j 的所有方案

接下來(lái)是狀態(tài)計(jì)算由于我們要找的是最后一個(gè)狀態(tài)的不同點(diǎn)，而第i - 1列伸到第 i 列的狀態(tài) j 是固定的， 沒(méi)有固定的是第i - 2列伸到第 i - 1列的狀態(tài)。

于是，集合的劃分依據(jù)應(yīng)是：i - 2 列延申到 i - 1 列的 狀態(tài)k 來(lái)劃分的；那么，我們上面的圖就應(yīng)該有所更新，表示為：這時(shí)，我們?cè)O(shè)第i - 2列的方塊的擺放方案狀態(tài)為k， 第 i - 1列方塊的擺放方案為 j。

此時(shí)，我們的集合劃分圖像應(yīng)當(dāng)如下

至此，完成所有分析,整體如下:

代碼如下:

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
							//N表行數(shù) 
const int N = 12, M = 1 << N;//M表方案數(shù)，一共有二的N次方個(gè) 
 
int n, m;
long long f[N][M]; //狀態(tài)轉(zhuǎn)移方程
vector<int> state[M];  //存儲(chǔ)所有合法狀態(tài) 
bool st[M]; //存儲(chǔ)每種狀態(tài)是否有奇數(shù)個(gè)連續(xù)的0，如果奇數(shù)個(gè)0是無(wú)效狀態(tài)
			//如果是偶數(shù)個(gè)零置為true。
 
 
int main()
{
	while(cin >> n >> m, n ||m)//本題有多個(gè)數(shù)據(jù) 
	{
		//第一部分：預(yù)處理1
		//對(duì)于每種狀態(tài)，先預(yù)處理每列不能有奇數(shù)個(gè)0 
		for(int i = 0;i < 1 << n;i ++)//預(yù)處理st數(shù)組,判斷所有連續(xù)的0是否有偶數(shù)個(gè)		 
		{
			int cnt = 0;//cnt 表示0的個(gè)數(shù)
			bool is_valid = true;//是否合法 
			 for(int j = 0;j < n;j ++)//遍歷這一列，從上到下 
			 if(i >> j & 1)//對(duì)于i的二進(jìn)制數(shù)的第j位,判斷是否為1 
			 {
			 	if(cnt & 1)//判斷前面的0是否有奇數(shù)個(gè) 
			 	{
			 		is_valid = false;//不合法 
			 		break;
				 }
				 cnt = 0;//清空 
			  } 
			  else cnt ++;//否則前面是0，cnt++ 
			  if(cnt & 1) is_valid = false;//判斷最下面那一段連續(xù)0的個(gè)數(shù) 
			  st[i] = is_valid;
		}
		
	//第二部分：預(yù)處理2
	//判斷第i - 2列伸出來(lái)的和第i - 1列伸出去的是否沖突
	
	for(int j = 0;j < 1 << n;j ++)//對(duì)于第i列的所有狀態(tài)
	{
		state[j].clear();//清空上次操作遺留的狀態(tài)(因?yàn)楸绢}有while循環(huán)，多個(gè)測(cè)試數(shù)據(jù))
		for(int k = 0;k < 1 << n;k ++)//對(duì)于第i-1列的所有狀態(tài) 
		{
			if((j & k)==0 && st[j | k])//若兩者伸出來(lái)的沒(méi)重疊
				state[j].push_back(k);//j | k表示當(dāng)前第i- 1列到底有幾個(gè)1，即哪幾行是放格子的 
									
		 } 
	}
	
	//第三部分：DP
	memset(f,0,sizeof f); //全部初始化為0，因?yàn)槭莣hile連續(xù)讀入 
	
	f[0][0] = 1;//這里沒(méi)有-1列，所以不可能有方塊伸到第0列，因此f[0][0] = 1, 即表示棋盤(pán)為空的一種狀態(tài) 
	
	for(int i =1;i <= m;i ++)//遍歷每一列:第i列合法范圍是(0~m-1列) 
		for(int j = 0;j < 1 << n;j ++)//遍歷當(dāng)前列（i）的所有狀態(tài)j 
			for(auto k: state[j])//遍歷第i-1列的狀態(tài)k,真正滿(mǎn)足則轉(zhuǎn)移 
				f[i][j] += f[i - 1][k];// 當(dāng)前列的方案數(shù)就等于之前的第i-1列所有狀態(tài)k的累加。
	
	//依據(jù)狀態(tài)表示的定義:f[m][0]表示 前m-1列都處理完，并且第m-1列沒(méi)有伸出來(lái)的所有方案數(shù)。
	//即整個(gè)棋盤(pán)處理完的方案數(shù) 
	cout << f[m][0] << endl;			
	}
	
	
	return 0;
}

注：第一部分的預(yù)處理，對(duì)應(yīng)上面分析的第二種情況， 

第二部分的預(yù)處理，對(duì)應(yīng)上面分析的第一種情況: