炮兵阵地
| Time Limit: 2000MS | Memory Limit: 65536K | |
| Total Submissions: 13114 | Accepted: 4806 |
Description
司 令部的将军们打算在N*M的网格地图上部署他们的炮兵部队。一个N*M的地图由N行M列组成，地图的每一格可能是山地（用"H" 表示），也可能是平原（用"P"表示），如下图。在每一格平原地形上最多可以布置一支炮兵部队（山地上不能够部署炮兵部队）；一支炮兵部队在地图上的攻击 范围如图中黑色区域所示：
如果在地图中的灰色所标识的平原上部署一支炮兵部队，则图中的黑色的网格表示它能够攻击到的区域：沿横向左右各两格，沿纵向上下各两格。图上其它白色网格均攻击不到。从图上可见炮兵的攻击范围不受地形的影响。
现在，将军们规划如何部署炮兵部队，在防止误伤的前提下（保证任何两支炮兵部队之间不能互相攻击，即任何一支炮兵部队都不在其他支炮兵部队的攻击范围内），在整个地图区域内最多能够摆放多少我军的炮兵部队。
如果在地图中的灰色所标识的平原上部署一支炮兵部队，则图中的黑色的网格表示它能够攻击到的区域：沿横向左右各两格，沿纵向上下各两格。图上其它白色网格均攻击不到。从图上可见炮兵的攻击范围不受地形的影响。
现在，将军们规划如何部署炮兵部队，在防止误伤的前提下（保证任何两支炮兵部队之间不能互相攻击，即任何一支炮兵部队都不在其他支炮兵部队的攻击范围内），在整个地图区域内最多能够摆放多少我军的炮兵部队。
Input
第一行包含两个由空格分割开的正整数，分别表示N和M；
接下来的N行，每一行含有连续的M个字符('P'或者'H')，中间没有空格。按顺序表示地图中每一行的数据。N <= 100；M <= 10。
接下来的N行，每一行含有连续的M个字符('P'或者'H')，中间没有空格。按顺序表示地图中每一行的数据。N <= 100；M <= 10。
Output
仅一行，包含一个整数K，表示最多能摆放的炮兵部队的数量。
Sample Input
5 4
PHPP
PPHH
PPPP
PHPP
PHHP
Sample Output
6
Source
题解：
状态压缩dp，用 mat[r] 记录 第 r 行的状态
dp[i][j][k] 表示 第 i 行 为状态 k 第 i - 1 行为状态 j 所能装的最多的大炮数
dp[i][j][k] = max(dp[i][j][k],dp[i - 1][l][k]+sum[i]);
枚举所有情况 即可
状态压缩dp，用 mat[r] 记录 第 r 行的状态
dp[i][j][k] 表示 第 i 行 为状态 k 第 i - 1 行为状态 j 所能装的最多的大炮数
dp[i][j][k] = max(dp[i][j][k],dp[i - 1][l][k]+sum[i]);
枚举所有情况 即可
1 #include<stdio.h>
2 #include<iostream>
3 #include<algorithm>
4 #include<cstring>
5 #include<cmath>
6 #include<queue>
7 #include<set>
8 #include<map>
9 #define Min(a,b) a>b?b:a
10 #define Max(a,b) a>b?a:b
11 #define CL(a,num) memset(a,num,sizeof(a));
12 #define inf 9999999
13 #define maxn 400
14 #define mod (1000000000 + 7)
15 #define eps 1e-6
16 #define ll long long
17 using namespace std;
18 int dp[110][70][70];
19 int mat[110],cnt ,stat[70],sum[70];
20 int ok(int x)
21 {
22 if(x&(x<<1)) return 0;
23 if(x&(x<<2)) return 0;
24 return 1;
25 }
26 int getsum(int x)
27 {
28 int sum = 0;
29 while(x > 0)
30 {
31 if(x&1)sum ++;
32 x>>=1 ;
33 }
34 return sum ;
35 }
36 void find(int x)
37 {
38 for(int i = 0 ; i < 1 << x; ++i)
39 {
40 if(ok(i))
41 {
42 stat[cnt] = i;
43 sum[cnt++] = getsum(i);
44 }
45 }
46 }
47 int main()
48 {
49 int row,col,i,j,k, l ;
50 char c;
51
52 scanf("%d%d",&row,&col);
53 cnt = 0 ;
54 getchar();
55 for( i = 0; i < row; ++i)
56 {
57 for( j = 0; j < col ;++j)
58 {
59 scanf("%c",&c);
60
61 if(c == 'H') mat[i]|=(1<<j);
62 }
63 getchar();
64 }
65
66 find(col);
67 CL(dp, -1);
68 for( i =0 ; i < cnt ;++i)
69 {
70 if(!(stat[i]&mat[0]))
71 dp[0][0][i] = sum[i] ;
72 }
73 for( i = 1 ; i < row ; ++i)
74 {
75 for( j = 0; j < cnt ; ++j)
76 {
77 if(stat[j]&mat[i])continue ;
78 for(k = 0 ; k < cnt ; ++k)// 第 i- 1 行的状态
79 {
80 if(stat[k]&stat[j])continue ;
81 for(l = 0 ; l < cnt; ++l)//第 i- 2 行的状态
82 {
83 if(stat[j]&stat[l])continue ;
84 if(dp[i - 1][l][k] == -1) continue ;//判断 第 i- 1 行 和第i-2行 合不合适
85 dp[i][k][j] = max(dp[i][k][j],dp[i - 1][l][k] + sum[j]);
86 }
87 }
88 }
89 }
90 int ans = -1 ;
91 for( i = 0 ; i < cnt; ++i)
92 {
93 for( j = 0 ; j < cnt; ++j)
94 {
95 ans = max(dp[row - 1][j][i],ans);
96 }
97 }
98 printf("%d\n",ans) ;
99
100 return 0;
101
102 }
2 #include<iostream>
3 #include<algorithm>
4 #include<cstring>
5 #include<cmath>
6 #include<queue>
7 #include<set>
8 #include<map>
9 #define Min(a,b) a>b?b:a
10 #define Max(a,b) a>b?a:b
11 #define CL(a,num) memset(a,num,sizeof(a));
12 #define inf 9999999
13 #define maxn 400
14 #define mod (1000000000 + 7)
15 #define eps 1e-6
16 #define ll long long
17 using namespace std;
18 int dp[110][70][70];
19 int mat[110],cnt ,stat[70],sum[70];
20 int ok(int x)
21 {
22 if(x&(x<<1)) return 0;
23 if(x&(x<<2)) return 0;
24 return 1;
25 }
26 int getsum(int x)
27 {
28 int sum = 0;
29 while(x > 0)
30 {
31 if(x&1)sum ++;
32 x>>=1 ;
33 }
34 return sum ;
35 }
36 void find(int x)
37 {
38 for(int i = 0 ; i < 1 << x; ++i)
39 {
40 if(ok(i))
41 {
42 stat[cnt] = i;
43 sum[cnt++] = getsum(i);
44 }
45 }
46 }
47 int main()
48 {
49 int row,col,i,j,k, l ;
50 char c;
51
52 scanf("%d%d",&row,&col);
53 cnt = 0 ;
54 getchar();
55 for( i = 0; i < row; ++i)
56 {
57 for( j = 0; j < col ;++j)
58 {
59 scanf("%c",&c);
60
61 if(c == 'H') mat[i]|=(1<<j);
62 }
63 getchar();
64 }
65
66 find(col);
67 CL(dp, -1);
68 for( i =0 ; i < cnt ;++i)
69 {
70 if(!(stat[i]&mat[0]))
71 dp[0][0][i] = sum[i] ;
72 }
73 for( i = 1 ; i < row ; ++i)
74 {
75 for( j = 0; j < cnt ; ++j)
76 {
77 if(stat[j]&mat[i])continue ;
78 for(k = 0 ; k < cnt ; ++k)// 第 i- 1 行的状态
79 {
80 if(stat[k]&stat[j])continue ;
81 for(l = 0 ; l < cnt; ++l)//第 i- 2 行的状态
82 {
83 if(stat[j]&stat[l])continue ;
84 if(dp[i - 1][l][k] == -1) continue ;//判断 第 i- 1 行 和第i-2行 合不合适
85 dp[i][k][j] = max(dp[i][k][j],dp[i - 1][l][k] + sum[j]);
86 }
87 }
88 }
89 }
90 int ans = -1 ;
91 for( i = 0 ; i < cnt; ++i)
92 {
93 for( j = 0 ; j < cnt; ++j)
94 {
95 ans = max(dp[row - 1][j][i],ans);
96 }
97 }
98 printf("%d\n",ans) ;
99
100 return 0;
101
102 }