炮兵阵地
时间限制： 2000 ms | 内存限制： 65535 KB 难度： 6 描述 司令部的将军们打算在N*M的网格地图上部署他们的炮兵部队。一个N*M的地图由N行M列组成，地图的每一格可能是山地（用"H" 表示），也可能是平原（用"P"表示），如下图。在每一格平原地形上最多可以布置一支炮兵部队（山地上不能够部署炮兵部队）；一支炮兵部队在地图上的攻击范围如图中黑色区域所示：如果在地图中的灰色所标识的平原上部署一支炮兵部队，则图中的黑色的网格表示它能够攻击到的区域：沿横向左右各两格，沿纵向上下各两格。图上其它白色网格均攻击不到。从图上可见炮兵的攻击范围不受地形的影响。
现在，将军们规划如何部署炮兵部队，在防止误伤的前提下（保证任何两支炮兵部队之间不能互相攻击，即任何一支炮兵部队都不在其他支炮兵部队的攻击范围内），在整个地图区域内最多能够摆放多少我军的炮兵部队。 输入 第一行输出数据测试组数X（0<X<100）
接下来每组测试数据的第一行包含两个由空格分割开的正整数，分别表示N和M； 接下来的N行，每一行含有连续的M个字符('P'或者'H')，中间没有空格。按顺序表示地图中每一行的数据。0<=N <= 100；0<=M <= 10。 输出 每组测试数据输出仅一行，包含一个整数K，表示最多能摆放的炮兵部队的数量。
样例输入
15 4PHPPPPHHPPPPPHPPPHHP
样例输出
6
来源
Noi 01
题解：
尚未有解，但附上标程供参考。
hzyqazasdf的代码：
/*为大家方便明白，注释比较多。该题可深化动态规划，学会滚动数组，状态压缩等知识。*/#include<iostream>#include <string.h>using namespace std;char map[101][11];//地图int surface[101];//地形状态压缩数int state[61];//所有的合法状态压缩数int stanum[61];//相应状态的炮兵数量int f[101][61][61];//动态规划存储矩阵int main(){int xx;cin>>xx;while(xx--){memset(map,0,sizeof(map));memset(surface,0,sizeof(surface));memset(state,0,sizeof(state));memset(stanum,0,sizeof(stanum));memset(f,0,sizeof(f));int row,col;cin>>row>>col;for (int i=0;i<row;i++)cin>>map[i];/*因为最大列数不大于10，故可用dp进行状态压缩注：所谓状态压缩即如：PHPP 可以用二进制0100表示，用十进制存储为4。本题因其反向对称性，为了方便压缩，故上边实例压缩成0010,用2表示，不影响求解。*/for (int i=0;i<row;i++)for (int j=0;j<col;j++){if(map[i][j] == 'H') surface[i] +=1<<j;}/*同地图状态压缩，对排列阵型的状态进行压缩，并算出相应阵型的数量。//如PHPP有0001 0010 1000 1001 摆法，相应的压缩为 1 2 6 7 相关人数为 1 1 1 2*/int snum=0;for(int i=0;i< 1<<col;i++){int temp=i;if( (i<<1)&i || (i<<2)&i ) continue;stanum[snum] = temp%2;while ( temp = (temp>>1) ) stanum[snum] += temp%2;state[snum++]=i;}/*动态规划状态转移方程：//f[i][j][k] = max{f[i-1][k][l]+stanum[j]},//f[i][j][k]表示第i行状态为s[j],第i-1行状态为s[k]的最大炮兵数//枚举l的每种状态,且state[j],state[k],state[l],地形互不冲突*///第一行放置所有炮兵情况for (int i=0;i<snum;i++){/*该处就表现出状态压缩的强大好处了，下边的语句进行状态和地形的判断//仅仅进行一次位与操作，即可知道是否摆放与地形冲突。以后状态判断类似*/if(state[i] & surface[0]) continue;f[0][i][0]=stanum[i];}//第二行放置所有炮兵情况for (int i=0;i<snum;i++){if(state[i] & surface[1]) continue;for (int k=0;k<snum;k++){if(state[k] & surface[0]) continue;if(state[i] & state[k]) continue;f[1][i][k] = f[1][i][k] > (f[0][k][0]+stanum[i]) ? f[1][i][k] : (f[0][k][0]+stanum[i]) ; }}//之后的炮兵放置情况。如果还是不明白，请仔细揣摩上边给出的动态规划状态转移方程for (int i=2;i<row;i++)for (int j=0;j<snum;j++){if(surface[i] & state[j]) continue;for(int k=0;k<snum;k++){if(surface[i-1] & state[k]) continue;if(state[j] & state[k]) continue;for (int l=0;l<snum;l++){if(state[l] & surface[i-2]) continue;if(state[j] & state[l] || state[k] & state[l]) continue;f[i][j][k] = f[i][j][k] > (f[i-1][k][l]+stanum[j]) ? f[i][j][k] : (f[i-1][k][l]+stanum[j]) ;}}}//找出最优解if(row ==0 ) cout<<"0"<<endl;else{int max=0;for (int i=0;i<snum;i++)for (int j=0;j<snum;j++){if(max<f[row-1][i][j]) max=f[row-1][i][j];}cout<<max<<endl;}}return 0;}/*另附网上经典的一个使用滚动数组的算法，以上算法为了方便大家阅读和理解，故进行分解演示。//明白该题核心算法之后，可以进一步优化，使用滚动数组。其依据为炮兵攻击范围上下2行，所以//任意行只与其相邻的两行相互影响，所以创建一个f[2][61][61]的滚动数据即可求解。//用滚动数组依次求出每行的最优解//roll为当前行,(roll+1)%2为前一行也即下一行//roll = 0;//for ( int i = 0; i < row; i++ ){//for ( int j = 0; j < snum; j++ ){//if ( (state[j]&surface[i]) ) continue;//状态j是否与i行地图冲突//if ( i == 0 ) f[roll][j][0] = stanum[j];//else if ( i == 1 ){//for ( int k = 0; k < snum; k++ ){//if ( (state[k]&surface[i-1]) ) continue;//if ( (state[j]&state[k]) ) continue;//if ( f[roll][j][k] < f[(roll+1)%2][k][0]+stanum[j] )//f[roll][j][k] = f[(roll+1)%2][k][0]+stanum[j];//}//}//else{//for ( int k = 0; k < snum; k++ ){//if ( (state[k]& surface[i-1]) ) continue;//状态k是否与i-1行地图冲突//if ( state[j]&state[k] ) continue; //状态j、k是否彼此冲突//for ( int l = 0; l < snum; l++ ){//if ( (state[l]& surface[i-2]) ) continue;//状态l是否与i-2行地图冲突//if ( (state[j]&state[l]) || (state[k]&state[l]) ) continue;//状态j、l、k是否彼此冲突//if ( f[roll][j][k] < f[(roll+1)%2][k][l]+stanum[j] )//f[roll][j][k] = f[(roll+1)%2][k][l]+stanum[j];//}//}//}//}//roll = (roll+1)%2;//}//roll = (roll+1)%2;*/
