[POJ1185][NOI2001]炮兵阵地 状压DP

题目链接:http://poj.org/problem?id=1185

很裸的状压,考虑对于一行用二进制储存每一种的状态,但是状态太多了做不了。

观察到有很多状态都是不合法的,于是我们预处理出合法的状态,发现只有60种,然后随便DP一下就可以了。

 #include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int N,M;
char G[][];
int s[],cnt[],scnt=,ban[];
int f[][][];
int main(){
memset(ban,,sizeof(ban));
memset(f,,sizeof(f));
memset(cnt,,sizeof(cnt));
memset(s,,sizeof(s));
scanf("%d%d",&N,&M);
for(int i=;i<=N;i++) scanf("%s",G[i]);
for(int i=;i<=N;i++)
for(int j=;j<M;j++)
if(G[i][j]=='H')
ban[i]|=(<<j);
int tmp=<<M;
for(int i=;i<tmp;i++){
bool flag=true;
for(int j=;j<M;j++){
int tmp=((i&(<<j))>)+((i&(<<j+))>)+((i&(<<j+))>);
if(tmp>){
flag=false;
break;
}
}
if(flag){
s[++scnt]=i;
for(int j=;j<M;j++)
if(i&(<<j))
cnt[scnt]++;
}
}
for(int i=;i<=scnt;i++)
if((s[i]&ban[])==)
f[][][i]=cnt[i];
for(int i=;i<=scnt;i++)
if((s[i]&ban[])==)
for(int j=;j<=scnt;j++)
if((s[i]&s[j])==&&(s[j]&ban[])==)
f[][j][i]=max(f[][j][i],f[][][j]+cnt[i]);
for(int i=;i<=N;i++)
for(int j=;j<=scnt;j++)
if((s[j]&ban[i-])==)
for(int k=;k<=scnt;k++)
if((s[j]&s[k])==&&(s[k]&ban[i-])==)
for(int t=;t<=scnt;t++)
if((s[j]&s[t])==&&(s[k]&s[t])==&&(s[t]&ban[i])==)
f[i][k][t]=max(f[i][k][t],f[i-][j][k]+cnt[t]);
int Ans=;
for(int i=;i<=scnt;i++)
for(int j=;j<=scnt;j++)
Ans=max(Ans,f[N][i][j]);
printf("%d\n",Ans);
return ;
}
上一篇:洛谷P2704 [NOI2001]炮兵阵地 [状压DP]


下一篇:poj1185 炮兵阵地 状压dp