Posted on 2012-03-21 19:41
C小加 閱讀(1962)
評論(0) 編輯 收藏 引用 所屬分類:
解題報告
又是周偉大牛論文里的例題。曾經做過一個只有兩行的題，很水的DP。矩陣加大后狀態也增加了很多，很自然的就用到了狀態壓縮。
但是，看了discuss之后覺得自己又一次弱爆了，那25行的代碼寫的都是神馬啊，看來只有膜拜的份了。還是先寫好狀態壓縮吧。
起初自己不會DFS，看了某位大牛的解題報告，理解了DFS并且表示這位大牛的DFS寫的太強大了，哦還有，周偉大牛的論文太強大了，哦還沒完，狀態壓縮后的二進制表示法太強大了，簡簡單單的0和1就把所有的狀態就搞定了。
發現vector在這里用很合適。
大牛博客地址：http://www.shnenglu.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;
}