POJ 2411 Mondriaan's Dream

想法：

狀態壓縮DP，我們定義一列(橫的)一個狀態D：

• 第i位置為1表示這一列位置i和下一列位置i是由直長方形組成(|)
• 第i位置為0表示1以外的情況

注意以上的定義，以這題題目的圖來看，

• 第一列狀態D1=(00100001100)2
• 第二列狀態D2=(11010010000)2
• 第三列狀態D3=(00100001001)2
• 其他列依此類推，最後一列一定全部都是0。

接下來定義dp[i][d] = k，表示第i列在狀態d的情況下有k個方法數。如果能接受的話，那麼根據定義，如果第H列是圖的最後一列，本題答案就是dp[H][0]。

    定義完成後，基本上的做法是從最上面那列開始往下更新，例如第i列狀態a如果能和第i+1列狀態b相鄰(注意任兩個狀態不一定相鄰..)，那麼dp[i+1][b]+=dp[i][a];，就這樣枚舉所有狀態，最後輸出答案dp[H][0]。

    為了簡化code，不用初始化第一列每個狀態方法數是1(因為第一列所有狀態都是可以的)，因此我們直接初始化dp[0][0]=1，令這個假設的第0列狀態0方法數為1。

    另外在做以上的for loop之前，先建個狀態是否可以相鄰的表，令adjacent[i][j] = true表示狀態i在這列而狀態j在下一列是可以相鄰的，如最上面題目example，adjacent[D1][D2]==true，adjacent[D2][D3]==true。

    最後總結一下，為了加速，我們可以總是讓寬比較小高比較大，這樣可以減少每列的狀態數，另外也能用個ans[H][W]來紀錄答案，如果重複的題目就直接輸出即可。

	#include <cstdio>
	#include <cstring>
	int H, W;
	bool adjacent[1<<11][1<<11];
	long long int dp[13][1<<11];
	long long int ans[13][13] = {0};
	bool AdjacentCheck(unsigned int, unsigned int);
	int main()
	{
	while (scanf("%d %d", &H, &W) && (H || W)) {
	if (ans[H][W]) {printf("%lld\n", ans[H][W]); continue;}
	if (H < W) {int tmp = H; H = W; W = tmp;} // make W small
	memset(dp, 0, sizeof(dp));
	memset(adjacent, 0, sizeof(adjacent));
	for (unsigned int i = 0; i < (1<<W); ++i)
	for (unsigned int j = 0; j < (1<<W); ++j)
	if (AdjacentCheck(i, j)) adjacent[i][j] = true;
	dp[0][0] = 1;
	for (int row = 0; row < H; ++row)
	for (unsigned int i = 0; i < (1<<W); ++i)
	for (unsigned int j = 0; j < (1<<W); ++j)
	if (adjacent[i][j]) dp[row+1][j] += dp[row][i];
	printf("%lld\n", dp[H][0]);
	ans[H][W] = ans[W][H] = dp[H][0];
	}
	}
	bool AdjacentCheck(unsigned int a, unsigned int b)
	{
	if ((a & b) != 0) return false;
	unsigned int ab = a | b;
	for (int i = 0; i < W; ) {
	if (ab & (1<<i)) ++i;
	else {
	if (i == W-1 || (ab & (1<<(i+1))) != 0) return false;
	else i+=2;
	}
	}
	return true;
	}

view raw [POJ] 2411 Mondriaan's Dream.cpp hosted with ❤ by GitHub