首页 > 代码库 > 洛谷P2704 炮兵阵地

洛谷P2704 炮兵阵地

P2704 炮兵阵地

题目描述

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

技术分享

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

输入输出格式

输入格式:

第一行包含两个由空格分割开的正整数,分别表示N和M;

接下来的N行,每一行含有连续的M个字符(‘P’或者‘H’),中间没有空格。按顺序表示地图中每一行的数据。N≤100;M≤10。

输出格式:

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

输入输出样例

输入样例#1:
5 4PHPPPPHHPPPPPHPPPHHP
输出样例#1:
6
首先预处理出每一行所有符合条件的状态s,0表示无炮,1表示有炮,并预处理出每种状态的炮数num[i]
处理出每一行的高低情况,1表示不能放, 0表示能放
定义状态F[i][j][k]表示前i行,第i行为k,第i - 1行为j的最大炮数,转移:
F[i][j][k] = max(F[i - 1][l][j] + num[k])
预处理出F[1][1][k] = num[k]
转移和预处理时注意判断状态的合法性
技术分享
  1 #include <cstdio>  2 #include <cstring>  3 #include <cstdlib>  4 #include <cstring>  5 #include <algorithm>  6 #include <vector>  7 #include <queue>  8 #include <stack>  9 inline void read(int &x){x = 0;char ch = getchar();char c = ch;while(ch < 0 || ch > 9)c = ch, ch = getchar();while(ch <= 9 && ch >= 0)x = x * 10 + ch - 0, ch = getchar();if(c == -)x = -x;} 10 inline int max(int a, int b){return a > b ? a : b;} 11  12 const int INF = 0x3f3f3f3f; 13 const long long MOD = 100000000; 14 const int MAXN = 100 + 10; 15 const int MAXM = 10 + 5;  16  17 int n,m; 18 int g[MAXN], k, s[100]; 19 int ans;int dp[MAXN][100][100];int num[100];  20  21 //找出二进制x中1的个数  22 inline int count(int x) 23 { 24     int tmp = 0; 25     while(x) 26     { 27         tmp ++;  28         x &= (x - 1); 29     } 30     return tmp; 31 } 32  33 //判断状态在水平方向上是否合法 34 inline int ok(int x) 35 { 36     if(x & (x << 1))return 0; 37     if(x & (x << 2))return 0; 38     return 1; 39 }  40  41 //判断状态x是否与第i行匹配  42 inline bool fit(int x, int i) 43 { 44     if(x & g[i])return 0; 45     return 1; 46 } 47  48 //初始化某一行所有可行的状态  49 inline void inits() 50 { 51     for(int i = 0;i < (1 << m);++ i) 52         if(ok(i))s[++k] = i, num[k] = count(i); 53 } 54  55 //初始化第i行的不可走状态  56 inline void initg() 57 { 58     for(int i = 1;i <= n;++ i) 59     { 60         for(int j= 1;j <= m;++ j) 61         { 62             char c = getchar(); 63             while(c != H && c != P)c = getchar(); 64             if(c == H)g[i] += (1 << (m - j)); 65         } 66     } 67 } 68   69 //初始化第一行的状态  dp、s: 0表示不放大炮,1表示放大炮  g:0表示可放大炮,1表示不可放大炮  70 inline void initdp() 71 { 72     //s中第一个状态是0,一定合法 73     for(int i = 1;i <= k;++ i) 74         if(fit(s[i], 1)) 75             dp[1][1][i] = num[i], ans = max(ans, dp[1][1][i]); 76 } 77  78 inline void DP() 79 { 80     for(int i = 2;i <= n;++ i) 81     { 82         for(int j = 1;j <= k;++ j) 83         { 84             if(!fit(s[j],i))continue; 85              86             for(int pre = 1;pre <= k;++ pre) 87             { 88                 if((s[pre] & s[j]) || (s[pre] & g[i - 1]))continue; 89                  90                 for(int pre2 = 1;pre2 <= k;++ pre2) 91                 { 92                     if((s[pre2] & s[j]) || (s[pre2] & s[pre]) || (s[pre2] & g[i - 2]))continue; 93                     dp[i][pre][j] = max(dp[i][pre][j], dp[i - 1][pre2][pre] + num[j]); 94                 } 95                 if(i == n) 96                     ans = max(ans, dp[i][pre][j]); 97             } 98         } 99     }100 }101 102 inline void out()103 {104     printf("%d", ans);105 }106 107 int main()108 {109     read(n);read(m);110     initg();111     inits();112     initdp(); 113     DP();114     out();115     return 0;116 }
View Code

洛谷P2704 炮兵阵地