首页 > 代码库 > poj1185：炮兵阵地（状压dp）
poj1185：炮兵阵地（状压dp）
也算是比较基础的状压dp了，跟做过的第二道比较又稍微复杂了一点
需要记录之前两行的状态。。
统计结果也稍有不同
另外还学习了一个得到一个整数二进制位 1 的个数的位运算方法
详见代码：
#include <iostream>#include <stdio.h>#include<string.h>#include<algorithm>#include<string>#include<ctype.h>using namespace std;#define MAXN 10000int s[70];int num[70];int cant[110];int dp[110][70][70];int ns;int n,m;int ct(int x){ int res=0; while(x) { res++; x&=(x-1); } return res;}void setstate(){ memset(num,0,sizeof(num)); for(int i=0;i<1<<10;i++) { if((i&(i<<1))==0&&((i&(i<<2))==0)) { s[ns]=i; num[ns++]=ct(i); } }}void ini(){ memset(cant,0,sizeof(cant)); char s[20]; for(int i=1;i<=n;i++) { scanf("%s",s); for(int j=0;j<m;j++) { if(s[j]==‘H‘) { cant[i]|=(1<<j); } } }}void solve(){ memset(dp,0,sizeof(dp)); for(int i=0;i<ns&&s[i]<(1<<m);i++) { if((s[i]&cant[1])==0) dp[1][0][i]=num[i]; } for(int i=2;i<=n;i++) { for(int t=0;t<ns&&s[t]<(1<<m);t++) { if(s[t]&cant[i]) continue; for(int j=0;j<ns&&s[j]<(1<<m);j++) { if(s[j]&cant[i-2]) continue; for(int k=0;k<ns&&s[j]<(1<<m);k++) { if(s[k]&cant[i-1]) continue; if(s[j]&s[k]) continue; if(s[t]&cant[i]) continue; if((s[t]&s[j])||(s[t]&s[k])) continue; dp[i][k][t]=max(dp[i][k][t],dp[i-1][j][k]+num[t]); } } } } int ans=0; for(int i=1;i<=n;i++) { for(int j=0;j<ns&&s[j]<(1<<m);j++) { for(int k=0;k<ns&&s[k]<(1<<m);k++) ans=max(ans,dp[i][j][k]); } } printf("%d\n",ans);}int main(){ ns=0; setstate(); while(scanf("%d%d",&n,&m)!=EOF) { ini(); solve(); } return 0;}
poj1185：炮兵阵地（状压dp）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。