【POJ 2411】Mondriaan's Dream【DP】

本文主要是介绍【POJ 2411】Mondriaan's Dream【DP】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目大意：

题目链接：http://poj.org/problem?id=2411
输出用$1\times 2$的骨牌覆盖$n\times m$的棋盘的方案数。

---

思路：

很明显是一道DP题目。
状压DP，每一行肯定是0或1。可以把它转化成十进制，用$p[i]$记录为$i$的情况能否拼好。
最终答案为$f[n][0]$

---

代码：

#include <cstdio>
#include <cstring>
using namespace std;long long f[12][2050];
int n,m;
bool p[2050];int main()
{while (scanf("%d%d",&n,&m),n&&m){memset(f,0,sizeof(f));memset(p,0,sizeof(p));f[0][0]=1;if ((n&1)&&(m&1))   //特判，肯定不能完成{printf("0\n");continue;}for (int i=0;i<(1<<m);i++)  //枚举每一个二进制{bool cnt=0,odd=0;for (int j=0;j<m;j++)if ((i>>j)&1)   //为1{odd|=cnt;  //是否是偶数if (odd) break;  //有连续技奇数个0就退出cnt=0;}else cnt^=1;  //记录0的个数是偶数还是奇数if (cnt) odd=1;p[i]=odd^1;}for (int i=1;i<=n;i++)for (int j=0;j<(1<<m);j++)for (int k=0;k<(1<<m);k++)  //枚举情况if ((!(j&k))&&p[j|k])  //可以拼好f[i][j]+=f[i-1][k];  printf("%lld\n",f[n][0]);	}return 0;
}

这篇关于【POJ 2411】Mondriaan's Dream【DP】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---