poj 1185(状压dp)

时间:2021-07-08 23:59:26

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

思路:状态压缩经典题目,dp[i][j][k]表示第i行状态为j,(i-1)行状态为k时最多可以放置的士兵个数,于是我们可以得到递推方程:dp[i][j][k]=max(dp[i][j][k],dp[i-1][k][l]+num[j]);(其中num[j]为该状态下可以放置的士兵的个数。至于具体怎么分析,这位大牛讲的很清楚:http://www.cnblogs.com/scau20110726/archive/2013/02/27/2935256.html

 #include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std; int dp[][][];
int row[];
int s[<<];//保存所有士兵合法的状态
int num[<<];
int n,m,ans,state;
char str[]; int Get_Num(int x)
{
int cnt=;
while(x>){
cnt++;
x=x&(x-);
}
return cnt;
} int main()
{
while(~scanf("%d%d",&n,&m)){
memset(row,,sizeof(row));
memset(dp,,sizeof(dp));
memset(num,,sizeof(num));
for(int i=;i<n;i++){
scanf("%s",str);
for(int j=;j<m;j++){
if(str[j]=='H')row[i]=(row[i]<<)|;
else row[i]<<=;
}
}
state=;
for(int i=;i<(<<m);i++){
if((i&(i<<))||(i&(i<<)))continue;
s[state]=i; //合法状态
num[state++]=Get_Num(i);//可以放置的士兵个数
}
for(int i=;i<state;i++){
if(s[i]&row[])continue;
dp[][i][]=num[i];
}
for(int i=;i<n;i++){
for(int j=;j<state;j++){
if(row[i]&s[j])continue;
for(int k=;k<state;k++){
if(s[j]&s[k])continue; //i行与i-1行士兵相互攻击
for(int l=;l<state;l++){
if(s[j]&s[l])continue;//i行与i-2行士兵相互攻击
if(s[k]&s[l])continue;//i-1行与i-2行士兵相互攻击
dp[i][j][k]=max(dp[i][j][k],dp[i-][k][l]+num[j]);
}
}
}
}
ans=;
for(int i=;i<state;i++){
for(int j=;j<state;j++){
ans=max(ans,dp[n-][i][j]);
}
}
printf("%d\n",ans);
}
return ;
}