首页 > 代码库 > poj1185（状压dp）
poj1185（状压dp）
题目连接：http://poj.org/problem?id=1185
题意：给出一张n*m的地图，‘H‘表示高地，不能部署炮兵，‘P‘表示平原，可以部署炮兵，炮兵之间必须保持横向、纵向至少2个格子的距离，保证没有误伤。问最多可以部署多少炮兵。
分析：对于每行大炮的状态仅与上两行的状态有关，因此要开个三维的数组来表示状态，当前行的状态可由前两行的状态转移而来。
当前行的最大值就是上一个状态的值加上当前状态中1的个数（当前行放大炮的个数）。
dp[i][j][k]表示到第i行时第i行的状态为j，第i-1行的状态为k的最大值，则dp[i][j][k] =max(dp[i][j][k],dp[i-1][k][l]+num[j]); num[j]为i状态中1的个数。
#include <cstdio>#include <cstring>#include <string>#include <cmath>#include <iostream>#include <algorithm>#include <queue>#include <cstdlib>#include <stack>#include <vector>#include <set>#include <map>#define LL long long#define mod 100000000#define inf 0x3f3f3f3f#define eps 1e-9#define N 100010#define FILL(a,b) (memset(a,b,sizeof(a)))#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1using namespace std;int dp[110][100][100],n,m,tot;int cur[110],state[100],num[100];char s[110][15];bool ok(int x){ if(x&(x<<1))return 0; if(x&(x<<2))return 0; return 1;}bool fit(int state,int k)//判断状态state在第k行是否符合{ if(state&cur[k])return 0; return 1;}void init()//预处理每行符合条件的所有状态{ int sum=1<<m; tot=0; for(int i=0;i<sum;i++) { if(ok(i))state[++tot]=i; }}int cal(int x)//计算该状态二进制的1的个数{ int res=0; while(x) { if(x&1)res++; x>>=1; } return res;}int main(){ while(scanf("%d%d",&n,&m)>0) { if(m+n==0)break; init(); for(int i=1;i<=n;i++)scanf("%s",s[i]+1); for(int i=1;i<=n;i++) { cur[i]=0; for(int j=1;j<=m;j++) { if(s[i][j]==‘H‘)cur[i]+=1<<(m-j); } } FILL(dp,0); for(int i=1;i<=tot;i++) { num[i]=cal(state[i]); if(fit(state[i],1))dp[1][i][1]=num[i]; } for(int i=2;i<=n;i++) { for(int j=1;j<=tot;j++) { if(!fit(state[j],i))continue; for(int k=1;k<=tot;k++) { if(!fit(state[k],i-1))continue; if(state[j]&state[k])continue; for(int l=1;l<=tot;l++) { if(state[l]&state[k])continue; if(state[l]&state[j])continue; if(i>2&&!fit(state[l],i-2))continue; dp[i][j][k]=max(dp[i][j][k],dp[i-1][k][l]+num[j]); } } } } int ans=0; for(int i=1;i<=n;i++) for(int j=1;j<=tot;j++) for(int k=1;k<=tot;k++) ans=max(ans,dp[i][j][k]); printf("%d\n",ans); }}
poj1185（状压dp）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。