Posted on 2012-03-20 21:11
C小加 閱讀(1810)
評(píng)論(1) 編輯 收藏 引用 所屬分類:
解題報(bào)告
弱爆了。我調(diào)試了一個(gè)下午加半個(gè)晚上，最后重寫(xiě)了一遍AC了。2xx ms的時(shí)間，在自己oj上排倒數(shù)第一。
我的第二道狀態(tài)壓縮DP，也是周偉論文《狀態(tài)壓縮》里的一道例題，核心思想這篇論文分析的很清楚，建議學(xué)習(xí)狀態(tài)壓縮的同學(xué)一定要看一下。
這道題做的很過(guò)癮，收獲很多，各種二進(jìn)制的解法。還有狀就是態(tài)數(shù)的求法也很強(qiáng)，剛開(kāi)始寫(xiě)的時(shí)候還準(zhǔn)備DFS呢，后來(lái)大牛告訴我直接枚舉所有狀態(tài)進(jìn)行刪除就可以了，好吧，刪除的判斷又是二進(jìn)制。
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int MAXM=63;
int e[103];
int m,n;
int s[MAXM];
int c[MAXM];
int f[103][MAXM][MAXM];
int cnt;
//輸入數(shù)據(jù)
void input()
{
memset(e,0,sizeof(e));
char str[13];
for(int i=0;i<m;i++)
{
scanf("%s",str);
for(int j=0;j<n;j++)
{
if(str[j]=='H') e[i]=(e[i]<<1)|1;
else e[i]=e[i]<<1;
}
}
}
//比較左右間隔是否為2
bool fit(int x)
{
if( x & (x<<1) ) return false;
if( x & (x<<2) ) return false;
return true;
}
//二進(jìn)制中1的個(gè)數(shù)
int num1(int x)
{
int count=0;
while(x>0)
{
count++;
x= x & (x-1);
}
return count;
}
//尋找狀態(tài)數(shù)
void DFS()
{
int total=1<<n;
for(int i=0;i<total;i++)
{
if(fit(i))
{
s[++cnt]=i;
c[cnt]=num1(i);
}
}
}
//DP
void DP()
{
//初始化
memset(f,-1,sizeof(f));
for(int i=0;i<=cnt;++i)
{
if(s[i]&e[0])continue;
f[0][i][0]=c[i];
}
for(int i=1;i<m;++i)
{
for(int j=0;j<=cnt;++j)
{
if(s[j]&e[i])continue;
for(int k=0;k<=cnt;++k)
{
if(s[j]&s[k])continue;
for(int l=0;l<=cnt;++l)
{
if(s[j]&s[l]) continue;
if(f[i-1][k][l]==-1) continue;
f[i][j][k]=max(f[i][j][k],f[i-1][k][l]+c[j]);
}
}
}
}
}
//輸出
void print()
{
int ans=0;
if(m!=0)
for(int i=0;i<=cnt;i++)
for(int j=0;j<=cnt;j++)
ans=max(ans,f[m-1][i][j]);
printf("%d\n",ans);
}
int main()
{
//freopen("in.txt","r",stdin);
while(scanf("%d %d",&m,&n)!=EOF)
{
cnt=-1;
input();
DFS();
DP();
print();
}
return 0;
}