首页 > 代码库 > 状态压缩经典题目(poj1184 nyoj81)
状态压缩经典题目(poj1184 nyoj81)
题目描述:
如果在地图中的灰色所标识的平原上部署一支炮兵部队,则图中的黑色的网格表示它能够攻击到的区域:沿横向左右各两格,沿纵向上下各两格。图上其它白色网格均攻击不到。从图上可见炮兵的攻击范围不受地形的影响。
现在,将军们规划如何部署炮兵部队,在防止误伤的前提下(保证任何两支炮兵部队之间不能互相攻击,即任何一支炮兵部队都不在其他支炮兵部队的攻击范围内),在整个地图区域内最多能够摆放多少我军的炮兵部队。
分析:这个题目有个简化版本 poj3254 ,觉得这个有难度的可以先做一下那个题目。
首先我们求的是最多能放多少个炮兵,那么假如我把所有的情况都枚举了,然后在得到的结果里面找一个最大值,那么是不是就可以了。其实这个题目的思想就是这么简单。
但是我们如果用一般的枚举的方法肯定会超时,那么就用到了状态压缩。
因为这个题目中一个炮影响的是两行,所以我们要多定义一维的状态来表示当前行的上上一行的状态。
状态:dp【i】【j】【k】 第 i 行,状态为 k ,第 i-1 行状态为 j 的最大放的炮兵数目;
转移方程 dp [ i ] [ k ] [ t ] = max ( dp [ i ] [ k ] [ t ] , dp [ i - 1 ] [ j ] [ k ] + num [ t ] );
代码:
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; #define Max(a,b) a>b?a:b int N,M; char num[110],top; int stk[70],cur[110]; int dp[110][70][70]; bool judge1(int x) //判断二进制有没有相邻的1 或者相隔2位 { if((x&(x<<1)) || (x&(x<<2))) return false; return true; } bool judge2(int i,int x) { return (cur[i]&stk[x]); } void jinit() { top=0; int i,total=1<<N; for(i=0; i<total; i++) if(judge1(i)) stk[++top]=i; } int jcount(int x) { int cnt=0; while(x) { if(x&1) cnt++; x>>=1; } return cnt; } int main() { int T; scanf("%d",&T); while(T--) { scanf("%d%d",&M,&N); jinit(); char x; int ans=0; for(int i = 1; i <= M; i++) { getchar(); cur[i]=0; for(int j=1; j<=N; j++) { scanf("%c",&x); if(x==‘H‘) cur[i]+=(1<<(j-1)); } } memset(dp,-1,sizeof(dp)); for(int i = 1; i <= top; i++) { num[i]=jcount(stk[i]); if(!judge2(1,i)) { dp[1][1][i]=num[i]; ans=Max(ans,num[i]); } } int i,t,j,k; for(i = 2; i <= M; i++) { for(t = 1; t <= top; t++) ///当前行 { if(judge2(i,t)) continue; for(j = 1; j <= top; j++) ///上上行 { if(stk[t]&stk[j])continue; for(k = 1; k <= top; k++) ///上一行 { if(stk[t]&stk[k])continue; if(dp[i-1][j][k]==-1)continue; dp[i][k][t] =max(dp[i][k][t],dp[i-1][j][k]+num[t]); ans = Max(ans,dp[i][k][t]); } } } } printf("%d\n",ans); } return 0; }
状态压缩经典题目(poj1184 nyoj81)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。