Posted on 2012-03-20 21:11
C小加 阅读(1766)
评论(1) 编辑 收藏 引用 所属分类:
解题报告
弱爆了。我调试了一个下午加半个晚上，最后重写了一遍AC了。2xx ms的时间，在自己oj上排倒数第一。
我的第二道状态压缩DP，也是周伟论文《状态压缩》里的一道例题，核心思想这篇论文分析的很清楚，建议学习状态压缩的同学一定要看一下。
这道题做的很过瘾，收获很多，各种二进制的解法。还有状就是态数的求法也很强，刚开始写的时候还准备DFS呢，后来大牛告诉我直接枚举所有状态进行删除就可以了，好吧，删除的判断又是二进制。
#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;
//输入数据
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;
}
//二进制中1的个数
int num1(int x)
{
int count=0;
while(x>0)
{
count++;
x= x & (x-1);
}
return count;
}
//寻找状态数
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;
}