Language:
炮兵阵地
Time Limit:2000MSMemory Limit:65536K
Total Submissions:20502Accepted:7944
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
Source
//dp[i][j][k] 代表 第一行状态为k,第 i-1 行状态为 j 的可能数#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>#include<queue>#include<stack>#include<vector>#include<set>#include<map>#define L(x) (x<<1)#define R(x) (x<<1|1)#define MID(x,y) ((x+y)>>1)#define eps 1e-8typedef __int64 ll;#define fre(i,a,b) for(i = a; i <b; i++)#define mem(t, v) memset ((t) , v, sizeof(t))#define sf(n)scanf("%d", &n)#define sff(a,b) scanf("%d %d", &a, &b)#define sfff(a,b,c) scanf("%d %d %d", &a, &b, &c)#define pfprintf#define bugpf("Hi\n")using namespace std;#define INF 0x3f3f3f3f#define N 105int dp[N][N][N],h[N],type[N];int n,m,k,num[N],ans;char a[N][N];bool judge(int x){if(x&(x<<1)) return false;if(x&(x<<2)) return false;return true;}int num_count(int x){int i=0;while(x){i++;x&=(x-1);}return i;}void inint(){int i,j;int len=1<<m;k=0;fre(i,0,len)if(judge(i))type[k++]=i;//同一行两个炮台的可能状态fre(i,0,k) num[i]=num_count(type[i]);//记录第 i 中状态中的 1 的个数（放炮台）}void solve(){int i,cur,up,uup;fre(i,2,n+1)fre(cur,0,k) //枚举第 i行的状态{if(h[i]&type[cur]) continue;fre(up,0,k) //枚举第i-1行状态{if(h[i-1]&type[up]||type[cur]&type[up]) continue;fre(uup,0,k)//枚举第i-2行状态{if(h[i-2]&type[uup]||type[cur]&type[uup]||type[up]&type[uup]&&!(dp[i-1][uup][up]))continue;dp[i][up][cur]=max(dp[i][up][cur],dp[i-1][uup][up]+num[cur]);if(dp[i][up][cur]>ans) ans=dp[i][up][cur];}}}pf("%d\n",ans);}int main(){ int i,j; sff(n,m);fre(i,1,n+1) {scanf("%s",a[i]+1); }mem(h,0); fre(i,1,n+1) fre(j,1,m+1)if(a[i][j]=='H')//不能放炮的地方标记，和后面状态取 & 和如果不为0就是不可以的状态h[i]|=1<<(j-1); //好好想想为什么减一 ，，非常重要 inint(); ans=0;mem(dp,0); fre(i,0,k) if(!(h[1]&type[i]))//初始第一行{dp[1][0][i]=num[i];if(num[i]>ans) ans=num[i];} solve();return 0;}
德有多高，艺有多深。
