C小加

厚德 博学 求真 至善 The bright moon and breeze
posts - 145, comments - 195, trackbacks - 0, articles - 0
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

poj 2411 Mondriaan's Dream(状态压缩DP)

Posted on 2012-03-21 19:41 C小加 阅读(1953) 评论(0)  编辑 收藏 引用 所属分类: 解题报告

又是周伟大牛论文里的例题。曾经做过一个只有两行的题,很水的DP。矩阵加大后状态也增加了很多,很自然的就用到了状态压缩。

但是,看了discuss之后觉得自己又一次弱爆了,那25行的代码写的都是神马啊,看来只有膜拜的份了。还是先写好状态压缩吧。

起初自己不会DFS,看了某位大牛的解题报告,理解了DFS并且表示这位大牛的DFS写的太强大了,哦还有,周伟大牛的论文太强大了,哦还没完,状态压缩后的二进制表示法太强大了,简简单单的01就把所有的状态就搞定了。

发现vector在这里用很合适。

 

大牛博客地址:http://www.cppblog.com/sdfond/archive/2009/07/31/91761.html

 

难点:1DFS寻找状态的过程。2、状态向上凸出和向下凸出的处理。

//poj 2411
//Time: 16MS Memory:1032K

#include<iostream>
#include<cstdio>
#include<vector>
#include<cstring>
using namespace std;
int m,n;
vector<int> v[1<<11];
long long f[13][1<<11];
//初始化
void init()
{
    for(int i=0;i<(1<<11);i++) v[i].clear();
    memset(f,0,sizeof(f));
}
//输入
bool input()
{
    scanf("%d %d",&m,&n);
    if(m<n) swap(m,n);
    if(m&&n) return true;
    else return false;
}
//寻找状态
void DFS(int x,int s1,int s2)//s1是s2的上一行状态
{
    if(x>=n)
    {
        if(s1<(1<<n)&&s2<(1<<n))
         v[s2].push_back(s1);
         return;
    }
    DFS(x+1,s1<<1|1,s2<<1);//s1为1,s2为0表示竖着摆放
    DFS(x+1,s1<<1,s2<<1|1);//s1为0表示竖着摆放的下半段,s2为1表示竖着摆放的上半段和横着摆放的半段
    DFS(x+2,s1<<2|3,s2<<2|3);//s1和s2都横着摆放,或者s1横着放,s2为两个竖着摆放的上半段
}
//DP
void DP()
{
    int total=1<<n;
    f[0][0]=1;//第0行的状态,全0表示此行已经被占满,不允许第一行向上凸出
    for(int i=1;i<=m+1;i++)
        for(int j=0;j<total;j++)
            for(int k=0;k<v[j].size();k++)
                f[i][j]+=f[i-1][v[j][k]];
}
//输出
void print()
{
    printf("%I64d\n",f[m+1][(1<<n)-1]);//第m+1行为全1状态,表示第m行没有凸出来的状态。
}
int main()
{
    while(input())
    {
        init();
        DFS(0,0,0);
        DP();
        print();

    }
    return 0;
}


 


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理