poj2411 Mondriaan's Dream （状压dp+多米诺骨牌问题）

这道题的解析这个博客写得很好

https://blog.csdn.net/shiwei408/article/details/8821853

大致意思就是我们可以只处理两行之间的关系，然后通过这两个关系推出所有行（有点像矩阵快速幂的思想）

几个要注意的地方

（1）第0行为全1

（2）发现自己的思维习惯还是先行在状态，我自己写得时候老是写反。

（3）path的个数可能有很多，不只是1<<n，可以输入极限数据然后输出路径的数目作为数组空间大小

（4）拿小的作列

（5）这道题是人为的设置一种方式，使得二进制与骨牌是一一对应的

如果是横放，就1 1 如果是竖放就 0 如果不放就是 1

                         11                        1                        0

然后这里的二进制操作非常的秀，要认真学习

#include<cstdio> #include<cstring> #include<algorithm> #define REP(i, a, b) for(int i = (a); i < (b); i++) #define _for(i, a, b) for(int i = (a); i <= (b); i++) using namespace std;typedef long long ll; const int MAXN = 15; ll dp[MAXN][2100]; int path[14000][2], p, n, m;void dfs(int l, int now, int pre) {if(l > m) return;if(l == m){path[p][0] = pre;path[p++][1] = now;return;}dfs(l + 2, (now << 2) | 3, (pre << 2) | 3);dfs(l + 1, (now << 1) | 1, pre << 1);dfs(l + 1, now << 1, (pre << 1) | 1); }int main() {while(~scanf("%d%d", &n, &m) && n){memset(dp, 0, sizeof(dp));if(m > n) swap(n, m);p = 0;dfs(0, 0, 0);dp[0][(1<<m)-1] = 1;_for(i, 1, n)REP(j, 0, p)dp[i][path[j][1]] += dp[i-1][path[j][0]];printf("%lld\n", dp[n][(1<<m)-1]);}return 0; }

 

转载于:https://www.cnblogs.com/sugewud/p/9819323.html

总结

以上是生活随笔为你收集整理的poj2411 Mondriaan's Dream （状压dp+多米诺骨牌问题）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。