本文主要是介绍Mondriaan's Dream （POJ - 2411，状压 DP），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
一.题目链接：
POJ-2411
二.题目大意：
有一个 n*m 大小的棋盘，往上摆满大小为 2*1 大小的木块，问有多少种不同的方法.
三.分析：
首先，明确一件事情：只需统计横放木块的合法方案数，对于一个合法横放木块状态来说，竖放木块只需插空即可，方案数为一.
设 dp[i][j] 表示横放木块放完了 1~ i-1 列，且第 i 列状态为 j 的方案数.
第 i 列的状态 j 是指第 i-1 列所横放的木块伸到第 i 列的二进制状态表示.
如上图，第 i 列的状态 j 为 1100010.
设第 i - 1 列的状态为 k.
易得合法的状态转移关系应满足一下两个条件：
① (j & k) == 0, 保证两个横放木块不会交叉.
② (j | k) 不能有奇数个连续的 0，保证了竖放木块能填满空格.
对于第二点，我们可以预处理出那些状态是合法的.
时间复杂度为
四.代码实现：
#include <cstdio>
#include <cstring>
using namespace std;typedef long long ll;const int M = (int)11;bool valid[(1<<M) + 5];
ll dp[M + 5][(1<<M) + 5];void init(int n)
{for(int i = 0; i < (1<<n); ++i){bool have_odd = 0, cnt = 0;for(int j = 0; j < n; ++j){if((i>>j) & 1)have_odd |= cnt, cnt = 0;elsecnt ^= 1;}valid[i] = !(have_odd | cnt);}
}int main()
{
// freopen("input.txt", "r", stdin);int n, m;while(~scanf("%d %d", &n, &m) && (n + m)){init(n);memset(dp, 0, sizeof(dp));dp[0][0] = 1;for(int i = 1; i <= m; ++i){for(int j = 0; j < (1<<n); ++j){for(int k = 0; k < (1<<n); ++k){if(!(j & k) && valid[j | k]){dp[i][j] += dp[i - 1][k];}}}}printf("%lld\n", dp[m][0]);}return 0;
}
这篇关于Mondriaan's Dream （POJ - 2411，状压 DP）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
