首页 > 代码库 > POJ1185 炮兵阵地 状态压缩DP
POJ1185 炮兵阵地 状态压缩DP
Description
如果在地图中的灰色所标识的平原上部署一支炮兵部队，则图中的黑色的网格表示它能够攻击到的区域：沿横向左右各两格，沿纵向上下各两格。图上其它白色网格均攻击不到。从图上可见炮兵的攻击范围不受地形的影响。
现在，将军们规划如何部署炮兵部队，在防止误伤的前提下（保证任何两支炮兵部队之间不能互相攻击，即任何一支炮兵部队都不在其他支炮兵部队的攻击范围内），在整个地图区域内最多能够摆放多少我军的炮兵部队。
Input
接下来的N行，每一行含有连续的M个字符(‘P‘或者‘H‘)，中间没有空格。按顺序表示地图中每一行的数据。N <= 100；M <= 10。
Output
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