Posted on 2012-03-21 19:41
C小加 阅读(1941)
评论(0) 编辑 收藏 引用 所属分类:
解题报告
又是周伟大牛论文里的例题。曾经做过一个只有两行的题，很水的DP。矩阵加大后状态也增加了很多，很自然的就用到了状态压缩。
但是，看了discuss之后觉得自己又一次弱爆了，那25行的代码写的都是神马啊，看来只有膜拜的份了。还是先写好状态压缩吧。
起初自己不会DFS，看了某位大牛的解题报告，理解了DFS并且表示这位大牛的DFS写的太强大了，哦还有，周伟大牛的论文太强大了，哦还没完，状态压缩后的二进制表示法太强大了，简简单单的0和1就把所有的状态就搞定了。
发现vector在这里用很合适。
大牛博客地址：http://www.cppblog.com/sdfond/archive/2009/07/31/91761.html
难点：1、DFS寻找状态的过程。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;
}