炮兵阵地
| Time Limit: 2000MS | Memory Limit: 65536K | |
| Total Submissions: 19217 | Accepted: 7421 |
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题，做过后还是觉得是比较简单的。
题意就不说了。。
分析：
首先看到范围M<=10 ,可以用状态压缩。
每一个格子放炮就是1，不放就是0；
1. 先不考虑地形，把一行的合法状态全部枚举出来，并且存下合法状态所对应的大炮数量。大概为不超过61种合法状态！
2. 求 i 行的最多放炮数量时就只要考虑前两行的状态和地形就可以了。。每次都只要前面一行的数据，可以用滚动数组优化空间！
状态：
dp【i】【j】【k】 第 i 行 j 状态，第 i-1 行 k 状态下的最优值。
为什么开三维的数组？
如果只是考虑前一行的状态，那么二维就行了。因为只受它影响。
而这里受前两行的影响，当要得到 i 行状态的最优值时 ， 要枚举 i-1 行 k状态的最优值，这时 k 状态是根据前面状态求出来的，即现在的第 i-2
行状态 可能就与 i 行的状态矛盾。那么证明了 二维数组时不够的。需要存下与这一行合法的前一行的状态！
状态转移方程：
dp【i】【j】【k】 = max（ dp【i】【j】【k】 ， dp【i-1】【k】【r】+sum【j】）
（1<=i<=n , 1<=j<=61 , 1<=k<=61 , 1<=r<=61）
边界：
因为每行都与 前两行有关系，所以边界就是 预处理出前两行的情况。。
/**Accepted 1744K 297MS **/
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int r,c,cnt;
char a[110][110];
int st[61];
int f[2][61][61];
int sum[61];
int surface[110];
int max(int fa,int fb)
{
return fa>fb?fa:fb;
}
bool can(int x) /**x是个大炮放置的状态图**/
{ /**按题意：大炮的左右两格 都不能有大炮**/
if(x& (x<<1) ) return false;
if(x& (x<<2) ) return false;
return true;
}
int getsum(int n) /**得到 n这个大炮放置的状态图的大炮数量。**/
{
int num=0;
while(n)
{
if(n&1) num++;
n>>=1;
}
return num;
}
void getst(int n)
{
int N= (1<<n);/** 所有状态的总数 **/
for(int i=0;i<N;i++)
{
if(can(i))
{
st[cnt] = i;
sum[cnt++] = getsum(i);
}
}
}
int main()
{
while(~scanf("%d%d",&r,&c))
{
for(int i=0;i<r;i++)
scanf("%s",a[i]);
/**把一行 合法的状态 预先算出**/
cnt=0;
getst(c);
/**把每行的地形状态 存下来。**/
memset(surface,0,sizeof(surface));
memset(f,0,sizeof(f));
for(int i=0;i<r;i++)
{
for(int j=0;j<c;j++)
{
if(a[i][j]=='H') surface[i] |= 1<<j;/**采用位运算**/
}
}
/**DP 预处理第一段**/
for(int i=0;i<cnt;i++)
{
if( surface[0] & st[i]) continue;/**地形状态 与 大炮放置状态 不能冲突**/
f[0][i][0] = sum[i];
}
/**预处理第二段**/
for(int i=0;i<cnt;i++)
{
if( surface[1] & st[i] ) continue;
for(int j=0;j<cnt;j++)
{
if(surface[0] & st[j]) continue;
if( st[i] & st[j] ) continue; /**相邻两行的 大炮状态图 不能冲突**/
f[1][i][j] = max(f[1][i][j] , f[0][j][0]+sum[i] );
}
}
int cur=0,pre=1;
/**DP处理其余段**/
for(int i=2;i<r;i++)
{
cur=pre^1;
for(int j=0;j<cnt;j++)
{
if( surface[i]&st[j] ) continue;
for(int k=0;k<cnt;k++)
{
if( surface[i-1] &st[k] ) continue;
if( st[j]&st[k] ) continue;
for(int r=0;r<cnt;r++)
{
if( surface[i-2] & st[r] ) continue;
if( (st[r]&st[j]) || (st[r]&st[k]) )continue;/**i行大炮不能与i-2行大炮冲突**/
f[cur][j][k] = max(f[cur][j][k], f[pre][k][r] +sum[j] );
//f[cur][j][k]=max(f[cur][j][k],f[(cur+1)%2][k][r]+sum[j]); /**真奇怪，用这种方法就WA**/
}
}
}
//cur=(cur+1)%2;
pre=cur;
}
/**枚举最后一行的 所有大炮状态图 求解!**/
int ans=0;
for(int i=0;i<cnt;i++)
for(int j=0;j<cnt;j++)
{
if(ans < f[cur][i][j] )
ans= f[cur][i][j];
}
printf("%d\n",ans);
}
return 0;
}
/**void display(int x)
{
int tt[100];int num=0;
while(x) {if(x&1) tt[++num]=1;else tt[++num]=0;x>>=1; }
for(int i=num;i>=1;i--)
{
cout<<tt[i];
}
cout<<endl;
}**/