POJ 1185 炮兵阵地(动态规划+状态压缩)

2013-08-23 来源: 凌乱的心 发布在  http://www.cnblogs.com/acm-bingzi/p/3278468.html

炮兵阵地

Description

司令部的将军们打算在N*M的网格地图上部署他们的炮兵部队。一个N*M的地图由N行M列组成,地图的每一格可能是山地(用"H" 表示),也可能是平原(用"P"表示),如下图。在每一格平原地形上最多可以布置一支炮兵部队(山地上不能够部署炮兵部队);一支炮兵部队在地图上的攻击范围如图中黑色区域所示: 

如果在地图中的灰色所标识的平原上部署一支炮兵部队,则图中的黑色的网格表示它能够攻击到的区域:沿横向左右各两格,沿纵向上下各两格。图上其它白色网格均攻击不到。从图上可见炮兵的攻击范围不受地形的影响。 
现在,将军们规划如何部署炮兵部队,在防止误伤的前提下(保证任何两支炮兵部队之间不能互相攻击,即任何一支炮兵部队都不在其他支炮兵部队的攻击范围内),在整个地图区域内最多能够摆放多少我军的炮兵部队。 

Input

第一行包含两个由空格分割开的正整数,分别表示N和M; 
接下来的N行,每一行含有连续的M个字符('P'或者'H'),中间没有空格。按顺序表示地图中每一行的数据。N <= 100;M <= 10。

Output

仅一行,包含一个整数K,表示最多能摆放的炮兵部队的数量。

Sample Input

5 4
PHPP
PPHH
PPPP
PHPP
PHHP

Sample Output

6

分析:思路很简单,因为每个位置要么放一门炮、要么不放,每行最多只有10个位置,所以可以用位存储状态,大体分如下两步:1.计算出每行所有的合法状态,并用位表示。2.DP~~~f[p][i][j] = Max{f[p-1][j][k]+ct(p,i)}    f[p][i][j]表示第p行取第i种方案,p-1行取第j种方案时的最大值,ct(p,i)表示第p行用第i种方案时用的炮的个数。

求整数x用二进制表示时1的个数,只需要让x不断的执行x &= (x-1)就可以了,执行了多少次就有多少个1。为什么呢??可以分两种情况,如果x最后一位是1,那么执行一次与运算可以把这个1消掉,但是如果最后一位是0呢??这个时候消掉的是最靠右的一个1,呵呵,可以简单的画一下看看。总之就是逐步消掉最后一个1,消了几次就有几个1啦~~

第一个代码如下:
 # include<iostream>
 # include<cstdio>
 # include<cstring>
 using namespace std;

 ;
 ;
 const int INF = 0xffffff;

 int n,m;
 ];    //ct[i][0]表示第i行放置炮的方案数,ct[i][j],j>0 表示第j种方案的状态
 ]; //tt[i]表示 i 表示成2进制时的1的个数,即放置炮的数目
 ][];    //f[p][i][j]表示第p行取第i种方案,p-1行取第j种方案时的最大值
 ][];
 char map[N][M];

 int max(int x,int y){
     return x>y ?x : y;
 }

 //这一行的状态
 void Init_row(const int &r,int x,int key){    //r是第几行,x表示2进制的位数,key表示状态
     if(x==m){
         ct[r][] ++;    //ct[r][0]表示这一行状态的数目
         ct[r][ct[r][]] = key;    //ct[r][i]表示第r行第i个状态 被压缩后的数字
         return ;
     }
     )== &&(key & )==)    //可以表示成状态
             Init_row(r,x+,(key<<)+);
         Init_row(r,x+,key<<);
 }

 bool Yes(int x,int y){    //判断map[x][y]能不能放置炮,会不会进入其他人射程
     int xx=x,yy=y;
     )  return hash[x][y];
     while(x||y){
         )== && (y&)==){
             hash[xx][yy] = false;
             break;
         }
         x>>=;
         y>>=;
     }
     )  hash[xx][yy] = ;
     hash[yy][xx] = hash[xx][yy];
     return hash[xx][yy];
 }

 void Dp(){
     int i,j,k,p,u,v,w;
     ;i<=ct[][];i++)  f[][i][] = tt[ct[][i]];    //第1行放置炮的数目
     )    //第2行放置炮的数目
         ;i<=ct[][];i++){
             u=ct[][i];
             ;j<=ct[][];j++){
                 f[][i][j] = -INF;
                 v = ct[][j];
                 if(Yes(u,v))
                     f[][i][j] = max(f[][i][j],f[][j][]+tt[u]);
             }
         }

     ;p<=n;p++){
         ;k<=ct[p][];k++){
             w=ct[p][k];
             ;i<=ct[p-][];i++){
                 v=ct[p-][i];
                 f[p][k][i] = -INF;
                 if(!Yes(v,w)) continue;
                 ;j<=ct[p-][];j++){
                     u=ct[p-][j];
                     if(Yes(u,v) && Yes(u,w))
                         f[p][k][i] = max(f[p][k][i],f[p-][i][j] + tt[w]);
                 }
             }
         }
     }
 }

 int main(){
     int i,j,temp,ans;
     memset(hash,-,sizeof(hash));
     ;i<;i++){
         temp = i;
         tt[i] = ;
         while(temp){    //整数temp表示成2进制时1的个数
             tt[i]++;
             temp &= (temp -);
         }
     }
     scanf("%d%d",&n,&m);
     ;i<=n;i++)
         scanf("%s",map[i]);
     ;i<=n;i++){
         ct[i][] = ;
         Init_row(i,,);
     }
     Dp();
     ans = -INF;
     )
         ;i<=ct[n][];i++)
             ans = max(ans,f[n][i][]);
     else{
         ;i<=ct[n][];i++)
             ;j<=ct[n-][];j++)
                 ans = max(ans,f[n][i][j]);
     }
     printf("%d\n",ans);
     ;
 }

  由于M很小,最多为10,所以可以对行进行状态压缩。二进制对应位为1表示放炮兵,为0表示空。我们可以事先生成所有有效的状态,即二进制数任何两个1都要相差两位以上,同时用数组记下此状态有多少个炮兵。对于地形也进行状态压缩,用1表求高地,0表示平原。判断某个状态能否放到某个地形,就是地形状态为1的地方,放置炮兵状态一定为0,这点可以用位运算解决。判断两个状态能否放在相邻行与此相同。

代码如下:
 # include <iostream>
 using namespace std;

 ;
 ;
 ;

 ][G][G];//滚动数组
 int ph[N],f[G];//ph数组用于判断状态在第i行是否满足在P的平原设置,f数组则存放满足的状态
 int n,m,g;//g为所有状态数

 int OneC(int x){//计算x二进制1的个数,这个算法很优秀,是在《编程之美》书中学到的。
     ;
     while(x){
         t ++;
         x &= (x-);
     }
     return t;
 }
 void DP(){//dp
     ; k < n ;k++){
         ; i< g; i++){
             if(ph[k] != (ph[k] | f[i]))continue;//判断状态f[i]是否满足在平原设置炮台
             ;j < g; j++){
                 ] != (ph[k-] | f[j]))continue;
                 if(f[i] & f[j])continue;//判断第k行和第k-1行的炮台是否有彼此击中
                 ; q< g; q ++){
                     ] != (ph[k-] | f[q]))continue;
                     if(f[q] & f[j])continue;
                     if(f[i] & f[q])continue;
                     d[k%][i][j] = max(d[k%][i][j], d[(k+)%][j][q] + OneC(f[i]));    //状态方程
                 }
             }
         }
     }
 }
 int main(){
     scanf("%d %d",&n,&m);
     int i ,j;
     char ch[M];
     ;i < n; i++){//计算ph[]
         ph[i] =;
         scanf("%s", ch);
         ; j < m; j++){
             if(ch[j] == 'P')
                 ph[i] += (<<(m-j-));
         }
     }
     <<m;
     ,g =; i< v;i++){//挑选合法状态
         )) == ) && (i & (i <<))==)//这个想法不错哦。
             f[g++] = i;
     }
     int pMax ;
     ){
         pMax = ;
         ; i<g ; i++){
             ] | f[i])==ph[])
                 pMax = max( pMax , OneC(f[i]));
         }
         printf("%d" ,pMax);
         ;
     }
     memset(d, ,sizeof(d));
     pMax = ;
     ; i < g; i++){//初始化d
         ] != (ph[] | f[i]))continue;
          ;j < g; j++){
             ] != (ph[] | f[j]))continue;
             ){
                 d[][i][j] = OneC(f[i]) + OneC(f[j]);
                 pMax = max (pMax , d[][i][j]);
             }
         }
     }
     ){
         printf("%d" ,pMax);
         ;
     }
     DP();
     ; i < g; i ++){
         ; j< g; j++){
             pMax = max( pMax ,d[(n+)%][i][j]);
         }
     }
     printf("%d", pMax);
     ;
 }

 代码如下:

 # include<cstdio>
 # include<string>
 # include<cstring>
 # include<iostream>
 # include<cmath>
 # include<algorithm>
 using namespace std;
 <<],cot[<<],dp[][][],a[];
 bool fit(int x,int y)
 {
     if(x&y)
         ;
     ;
 }
 void init()
 {
      sum=<<m;num=;
     ;i<sum;i++)
     {
         )||i&(i<<))
             continue;
         sta[num]=i;
         ;
         while(temp)
         {
                 count++;
             temp&=temp-;
         }
         cot[num++]=count;
     }
 }
 void DP()
 {
     ;
     ;i<num;i++)
     {
         ],sta[i]))
             continue;
         dp[][][i] = cot[i];
         ][][i])
                 ans=dp[][][i];
     }
     ;i<=n;i++)
         ;j<num;j++)
             ;k<num;k++)
             {
                 ],sta[j]))
                     continue;
                 ;l<num;l++)
                 {
                     ],sta[l])||!dp[i-][l][j])
                         continue;
                     dp[i][j][k]=max(dp[i][j][k],dp[i-][l][j]+cot[k]);
                     if(ans<dp[i][j][k])
                         ans=dp[i][j][k];
                 }
             }
             printf("%d\n",ans);
 }
 int main()
 {
     char s;
     scanf("%d%d",&n,&m);
     getchar();
     init();
     ;i<=n;i++)
     {
         ;j<=m;j++)
         {
             scanf("%c",&s);
             if(s=='H')
             {
                 <<(j-);
                 a[i]+=tem;
             }
         }
         getchar();
     }
     DP();
     ;
 }
另附转的一篇http://www.cnblogs.com/acm-bingzi/p/3278901.html

相关文章