POJ 2411 Mondriaan's Dream 解题报告
（原文链接http://hi.baidu.com/newmyl/blog/item/b1d3c609fd6009206b60fbb1.html）
这题的DFS+DP解法：
当高度和宽度都为奇数时显然答案为0, 这个用面积的奇偶性就很容易得证记f[i][s1]为第i-1行全满且第i行状态为s1时的种数，便有如下递推关系:
f[i][s1] = sigma(f[i-1][s2]);
其中(s1, s2)整体作为一个放置方案， 这样f[h+1][0]即是答案了
对于每一个位置，我们有三种放置方法：
1. 竖直放置
2. 水平放置
3. 不放置
d为当前列号 ，初始化d, s1, s2都为0;对应以上三种放置方法，s1, s2的调整为:
1. d = d + 1, s1 << 1 | 1, s2 << 1;
2. d = d + 2, s1 << 2 | 3, s2 << 2 | 3;
3. d = d + 1, s1 << 1, s2 << 1 | 1;
先就第一种情况解释一下，另外的两种情况可以类推
S1<<1|1即为把s1的二进制表示后面加上一个1，对就于本题来说就是(d+1)列上放置，s2<<1即为把s2的二进制表示后面加上一个0，对于本题来说就是(d+1)列上不放置。
但为什么s1、s2会如此变化呢？s1对应于本行的状态，s2对应于上一行的状态，能竖直放置意味着上一行的(d+1)列是空着的，因此此时上一行的状态为s2<<1，同时竖置放置了之后，则本行(d+1)行放置了东西，状态于是变为s1<<1|1;
当d == w时保存状态
对于初始时的f值，可以假设第0行全满，第一行只有两种放法:
1. 水平放置 d = d + 2, s << 2 | 3;
2. 不放置 d = d + 1, s << 1;
另外，利用滚动数组，可以减少空间的开销
还有一个可以提高较率的地方，当输入的 w > h 时，对调，因为横向的运算是指数
级的， 而列向的是线性的.
附代码：
# include <stdio.h>
# include <string.h>
__int64 a[2][3000];
int t,n,m;
void dfs(int d,int mm) //d表示列数，mm表示状态
{
if(d==m)
{
a[0][mm]++;
return;
}
if(d+1<=m)
dfs(d+1,mm<<1);
if(d+2<=m)
dfs(d+2,mm<<2|3);
}
void DFS(int d,int mm,int nn)//mm对应于上一行状态，nn对应于下一行状态
{
if(d==m) //若全部的列都确定状态，就把此状态的放法数加到nn状态里
{
a[t][nn]+=a[(t+1)%2][mm];
return;
}
if(d+1<=m) //如上所说
{
DFS(d+1,mm<<1,nn<<1|1);
DFS(d+1,mm<<1|1,nn<<1);
}
if(d+2<=m)
DFS(d+2,mm<<2|3,nn<<2|3);
}
int main()
{
int i;
while(scanf("%d%d",&n,&m)&&n&&m)
{
if((n*m)%2) //根据面积
{
printf("0\n");
continue;
}
if(n>m)
n^=m,m^=n,n^=m; //交换
memset(a,0,sizeof(a));
dfs(0,0);//初始化第一行
for(i=2;i<=n;i++)
{
t=(i+1)%2; //滚动数组的第一个下标计算
DFS(0,0,0);
memset(a[(t+1)%2],0,sizeof(a[0]));//清空另一行
}
printf("%I64d\n",a[(n+1)%2][(1<<m)-1]); //输出最后一行全部放满的结果。
}
return 0;
}
别附打表代码：
# include <stdio.h>
__int64 a[11][11]={0,1,0,1,0,1,0,1,0,1,0,1,2,3,5,8,13,21,34,55,89,144,0,3,0,11,0,41,0,153,0,571,0,1,5,11,36,95,281,781,2245,6336,18061,51205,0,8,0,95,0,1183,0,14824,0,185921,0,1,13,41,281,1183,6728,31529,167089,817991,4213133,21001799,0,21,0,781,0,31529,0,1292697,0,53175517,0,1,34,153,2245,14824,167089,1292697,12988816,108435745,1031151241,8940739824,0,55,0,6336,0,817991,0,108435745,0,14479521761,0,1,89,571,18061,185921,4213133,53175517,1031151241,14479521761,258584046368,3852472573499,0,144,0,51205,0,21001799,0,8940739824,0,3852472573499,0};
int main()
{
int n,m;
while(scanf("%d%d",&n,&m)&&n&&m)
printf("%I64d\n",a[n-1][m-1]);
return 0;
} |
