登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

银河里的星星

落在人间

 
 
 

日志

 
 

poj 2411 Mondriaan's Dream 状态dp  

2008-10-30 10:41:24|  分类: 算法与acm |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

题目的意思是这样的:http://acm.pku.edu.cn/JudgeOnline/problem?id=2411

给你一个h*w的矩形,用一个1*2的小矩形去填充,问有多少种填充方法,不考虑对称性。

 

关键点提示:

 1.DFS部分

实际上是在枚举第i行的放置方法,由此便可以确定出该行及上一行的状态。

对于第i行,状态(参数next_stat)的定义是指,前i-1行完全放满,第i行的所有位置是否放置(0,1表示)组成的二进制序列,转化为十进制数后所代表的状态。

放置方法,总共存在三种,
1. 竖直放置
2. 水平放置
3. 不放置

以竖直放置举例说明:

假设第i行的第3列位置是要竖直放置,则说明它的前一行该列位置必然是0,放置后这一行的状态必然变成了1,所以上一行的状态应该是prev_stat << 1,该行是(next_stat << 1)|1,直到column == w,即从左到右开始枚举,枚举到了最右列,说明该放置方案完毕。

本质上是枚举的第i行的放置方案,而放置方案实际上确定了上下两行的状态。

2.注意到prev_stat并没有明确指明列值,对于列的变化实际上是通过移位来反映的。

prev_stat,next_stat初始均为0,第一次移位确定的是左边第一个位置的状态,这样随着移位的进行这个状态不断的往高位迁移,这样在以后的移位,或运算中保证保持不变。也就是说,随着移位的进行,本来第一位表示的是最左边那列的状态,慢慢得变成第2,3,4,...w位来表示它的状态,实际上是该状态值不断得伴随着移位再向高位迁移。

 

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 <cstdio>
#include <cstring>
#include <cstdlib>
#define MAX (1<<11)+1
int w;
long long a[2][MAX];
int t;

//DFS枚举第i行的放置情况(保证第i-1行放满),由此确定该行及第i-1行的状态,为节约空间,使用滚动数组实现
void DFS(int column,int next_stat,int prev_stat){
    if(column == w){a[t][next_stat] += a[(t+1)%2][prev_stat];return;}
    if(column + 1 <= w){
        DFS(column+1,next_stat << 1 , (prev_stat << 1)|1);//不放置
        DFS(column+1,(next_stat << 1)|1,prev_stat << 1); //竖直放置      
    }
    if(column + 2 <= w)
        DFS(column+2,(next_stat << 2)| 3,(prev_stat << 2)|3);//水平放置
}

int main(){
    int h;
    while(scanf("%d%d",&h,&w) &&(h != 0 || w != 0)){
        if(h == 0 || w == 0 || (h*w)%2 == 1){printf("0\n");continue;}
        if(w > h){ w ^= h; h ^= w; w ^= h;}
        memset(a,0,sizeof(a));
        t = 0;
        a[t][(1 << w) - 1] = 1;//初始化,相当于第0行全满,所以只有该状态数为1,其他状态方法均为0.
        for(int i = 1 ; i <= h ; i++){
                t = (t+1)%2;
                DFS(0,0,0);
                memset(a[(t+1)%2],0,sizeof(a[0]));
        }
        printf("%I64d\n",a[t][(1 << w) -1]);
    }
    return 0;
}

/*

//printf-table
# 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;
}

*/

 

  评论这张
 
阅读(1664)| 评论(0)

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018