首页 > 代码库 > POJ1185 炮兵阵地 状态压缩DP

POJ1185 炮兵阵地 状态压缩DP

B - 炮兵阵地
Time Limit:2000MS     Memory Limit:65536KB     64bit IO Format:%I64d & %I64u
Submit Status
Appoint description: 

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 4PHPPPPHHPPPPPHPPPHHP

Sample Output

6


转自 :http://chuanwang66.iteye.com/blog/1467227

1. 为何状态压缩:

    棋盘规模为n*m,且m≤10,如果用一个int表示一行上棋子的状态,足以表示m≤10所要求的范围。故想到用int s[num]。至于开多大的数组,可以自己用DFS搜索试试看;也可以遍历0~2^m-1,对每个数值的二进制表示进行检查;也可以用数学方法(?)

 

2. 如何构造状态:

    当然,在此之前首先要想到用DP(?)。之后,才考虑去构造状态函数f(...)。

    这里有一个链式的限制 :某行上的某个棋子的攻击范围是2。即,第r行的状态s[i],决定第r-1行只能取部分状态s[p];同时,第r行的状态s[i],第r-1行状态s[p],共同决定第r-2行只能取更少的状态s[q]。当然,最后对上面得到的候选s[i], s[p], s[q],还要用地形的限制去筛选一下即可。

    简言之,第r行的威震第r-2行,因此在递推公式(左边=右边)中,必然同时出现r,和r-2两个行标;由于递推公式中行标是连续出现的,故在递推公式中必然同时出现r, r-1和r-2三个行标。由于在递推公式中左边包含一个f(...),右边包含另一个f(...),根据抽屉原理,r, r-1, r-2中至少有两个在同一个f(...)中,因此状态函数中必然至少包括相邻两行的行号作为两个维度。这就是为什么状态函数要涉及到两(相邻的)行,而不是一行。能想到的最简单形式如下:

    dp[r][i][p]:第r行状态为s[i],第r-1行状态为s[p],此时从第0行~第r行棋子的最大数目为dp[r][i][p]

 

    递推公式:

 

                                                s[p]影响到s[q]的选取

                                                          ----

                                                         |    |

                  dp[r][i][p]=max{dp[r-1][p][q]}+sum[j], 其中sum[j]是状态s[j]中1的个数

                           |   |                             |

                           ----                             |

               s[i]影响到s[p]的选取                 |

                           |                                 |

                           ----------------------------

 

 

转自:http://www.cnblogs.com/ZShogg/archive/2013/05/11/3072534.html

 

题意:给出一张n*m的地图,‘H‘表示高地,不能部署炮兵,‘P‘表示平原,可以部署炮兵,炮兵之间必须保持横向、纵向至少2个格子的距离,保证没有误伤。问最多可以部署多少炮兵。

分析:

1.可以用一个32位整数存每一行的状态(二进制上1表示有布置炮兵,0表示没有布置炮兵),由于每一行的状态都要前两行的状态来决定,因此真正的一个状态应该包含本行的状态和上一行的状态,用dp[x][i][j]表示第x行上状态i,x-1行状态为j的最优解。

2.每一行的状态其实只有60种,可以直接暴力搜索出来,把这60种状态按二进制递增顺序(排序目的是方便确定状态没有超出n*m的范围)存到数组state[]中,计算好每种状态中能部署炮兵的数目,存到get[]数组。

3.地图转换成一个二进制的数组,即一个整数表示一行的地形(1表示高地,0表示平原)。因此一个状态能否存在的一个条件是state[i] & map[x] == 0,这样是合法的.  (注意取反存,方便判断)

4.状态转移方程为dp[x][i][j] = max(dp[x - 1][j][k] + get[i],dp[x][i][j]),条件是state[i] & map[x] == 0 ,state[i] & state[j] == 0,state[i] & state[k] == 0,而且存在dp[x - 1][j][k]。把不存在的dp[x][i][j]标为-1.

PS:看了discuss发现还可以用最大点独立集来做。

 

上面的链接 还有相关滚动数组的做法,orz。

 

经典就是经典啊~~~~~

注意点:

1.状态涉及本行与上行。

2.需要先筛选一遍可行状态,不然会T。

3.要将地形压缩,不然会T。压缩时取反,高地表示1.

4.还可以用滚动数组做~~

 

  1 #include<iostream>  2 #include<cstring>  3 #include<cstdlib>  4 #include<cstdio>  5 #include<algorithm>  6 #include<cmath>  7 #include<queue>  8 #include<map>  9 #include<vector> 10  11 #define N 10005 12 #define M 100000 13 #define mod 1000000007 14 #define mod2 100000000 15 #define ll long long 16 #define maxi(a,b) (a)>(b)? (a) : (b) 17 #define mini(a,b) (a)<(b)? (a) : (b) 18  19 using namespace std; 20  21 int n,m; 22 char s[110][20]; 23 int dp[110][110][110]; 24 int a[110]; 25 int ans; 26 int tot; 27 int cc[ (1<<10)+10 ]; 28 int ok[ (1<<10)+10 ]; 29  30 void ini1() 31 { 32     int i,j; 33     for(i=0;i<(1<<10);i++){ 34         for(j=0;j<10;j++){ 35             if( ( (i&(1<<j))!=0) ){ 36                 cc[i]++; 37             } 38         } 39     } 40 } 41  42 bool isok(int x) 43 { 44     if(x&(x<<1))return false; 45     if(x&(x<<2))return false; 46     return true; 47 } 48  49  50 void ini2() 51 { 52     memset(ok,0,sizeof(ok)); 53     for(int i=0;i<(1<<m);i++) //i枚举所有m位的二进制数 54     { 55         if(isok(i)) 56         { 57             ok[tot]=i; 58             tot++; 59         } 60     } 61 } 62  63 void ini() 64 { 65     int i,j; 66     ans=0; 67    // tot=1<<m; 68     tot=0; 69     ini2(); 70     memset(dp,0,sizeof(dp)); 71     memset(a,0,sizeof(a)); 72     for(i=1;i<=n;i++){ 73         scanf("%s",s[i]); 74     } 75     //a[0]=a[1]=tot-1; 76     for(i=1;i<=n;i++){ 77         for(j=0;j<m;j++){ 78             if( s[i][ j ]==H ){ 79                 a[i]+=(1<<j); 80             } 81         } 82     } 83  84    // for(i=1;i<=n;i++){ 85     //    printf("  i=%d a=%d\n",i,a[i]); 86     //} 87 } 88  89  90 void solve() 91 { 92     int o,i,j,k; 93     for(i=1;i<=n;i++){ 94         for(o=0;o<tot;o++){ 95             if( (ok[o] & a[i] )!=0 ) continue; 96             if(i==1){ 97                 dp[i][o][0]=cc[ ok[o] ];continue; 98             } 99             for(j=0;j<tot;j++){100                 if( (ok[j] & a[i-1] )!=0 ) continue;101                 if( (ok[o] & ok[j] )!=0 ) continue;102                 for(k=0;k<tot;k++){103                     if( (ok[k] & a[i-2] )!=0 ) continue;104                     if( (ok[o] & ok[k] )!=0 ) continue;105                     if( (ok[j] & ok[k] )!=0 ) continue;106                     //printf("   i=%d o=%d j=%d k=%d cco=%d ccj=%d dp=%d\n",i,ok[o],ok[j],ok[k],cc[ ok[o] ],cc[ ok[j] ],dp[i-2][ok[k]]);107                     dp[i][o][ j ]=max(dp[i][ o ][ j ],cc[ ok[o] ]+dp[i-1][ j ][ k ]);108                 }109             }110         }111     }112 113     i=n;114     for(o=0;o<tot;o++){115         for(j=0;j<tot;j++)116         ans=max(ans,dp[i][ o ][ j ]);117     }118 119     //for(i=1;i<=n;i++){120    //     for(o=0;o<tot;o++) printf(" i=%d o=%d dp=%d\n",i,ok[o],dp[i][ok[o]]);121    // }122 }123 124 int main()125 {126     ini1();127     //freopen("data.in","r",stdin);128     //freopen("data.out","w",stdout);129     //scanf("%d",&T);130    // for(int cnt=1;cnt<=T;cnt++)131    // while(T--)132     while(scanf("%d%d",&n,&m)!=EOF)133     {134         ini();135         solve();136         printf("%d\n",ans);137        // printf("%d\n",ma);138         //cout<<tot<<endl;139     }140 141     return 0;142 }

 

POJ1185 炮兵阵地 状态压缩DP