炮兵阵地
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 分析：思路很简单，因为每个位置要么放一门炮、要么不放，每行最多只有10个位置，所以可以用位存储状态，大体分如下两步：
1.计算出每行所有的合法状态，并用位表示。
2.DP～～～
f[p][i][j] = Max{f[p-1][j][k]+ct(p,i)} f[p][i][j]表示第p行取第i种方案，p-1行取第j种方案时的最大值，ct(p,i)表示第p行用第i种方案时用的炮的个数。 求整数x用二进制表示时1的个数，只需要让x不断的执行x &= (x-1)就可以了，执行了多少次就有多少个1。
为什么呢？？可以分两种情况，如果x最后一位是1，那么执行一次与运算可以把这个1消掉，但是如果最后一位是0呢？？这个时候消掉的是最靠右的一个1，呵呵，可以简单的画一下看看。总之就是逐步消掉最后一个1，消了几次就有几个1啦～～ 第一个代码如下：
# include<iostream>
# include<cstdio>
# include<cstring>
using namespace std; const int N = ;
const int M = ;
const int INF = 0xffffff; int n,m;
int ct[N][]; //ct[i][0]表示第i行放置炮的方案数，ct[i][j],j>0 表示第j种方案的状态
int tt[]; //tt[i]表示 i 表示成2进制时的1的个数，即放置炮的数目
int f[N][][]; //f[p][i][j]表示第p行取第i种方案，p-1行取第j种方案时的最大值
int hash[][];
char map[N][M]; int max(int x,int y){
return x>y ?x : y;
} //这一行的状态
void Init_row(const int &r,int x,int key){ //r是第几行，x表示2进制的位数，key表示状态
if(x==m){
ct[r][] ++; //ct[r][0]表示这一行状态的数目
ct[r][ct[r][]] = key; //ct[r][i]表示第r行第i个状态 被压缩后的数字
return ;
}
if(map[r][x] == 'P' && (key & )== &&(key & )==) //可以表示成状态
Init_row(r,x+,(key<<)+);
Init_row(r,x+,key<<);
} bool Yes(int x,int y){ //判断map[x][y]能不能放置炮，会不会进入其他人射程
int xx=x,yy=y;
if(hash[x][y] != -) return hash[x][y];
while(x||y){
if((x&)== && (y&)==){
hash[xx][yy] = false;
break;
}
x>>=;
y>>=;
}
if(hash[xx][yy] == -) hash[xx][yy] = ;
hash[yy][xx] = hash[xx][yy];
return hash[xx][yy];
} void Dp(){
int i,j,k,p,u,v,w;
for(i=;i<=ct[][];i++) f[][i][] = tt[ct[][i]]; //第1行放置炮的数目
if(n>=) //第2行放置炮的数目
for(i=;i<=ct[][];i++){
u=ct[][i];
for(j=;j<=ct[][];j++){
f[][i][j] = -INF;
v = ct[][j];
if(Yes(u,v))
f[][i][j] = max(f[][i][j],f[][j][]+tt[u]);
}
} for(p=;p<=n;p++){
for(k=;k<=ct[p][];k++){
w=ct[p][k];
for(i=;i<=ct[p-][];i++){
v=ct[p-][i];
f[p][k][i] = -INF;
if(!Yes(v,w)) continue;
for(j=;j<=ct[p-][];j++){
u=ct[p-][j];
if(Yes(u,v) && Yes(u,w))
f[p][k][i] = max(f[p][k][i],f[p-][i][j] + tt[w]);
}
}
}
}
} int main(){
int i,j,temp,ans;
memset(hash,-,sizeof(hash));
for(i=;i<;i++){
temp = i;
tt[i] = ;
while(temp){ //整数temp表示成2进制时1的个数
tt[i]++;
temp &= (temp -);
}
}
scanf("%d%d",&n,&m);
for(i=;i<=n;i++)
scanf("%s",map[i]);
for(i=;i<=n;i++){
ct[i][] = ;
Init_row(i,,);
}
Dp();
ans = -INF;
if(n==)
for(i=;i<=ct[n][];i++)
ans = max(ans,f[n][i][]);
else{
for(i=;i<=ct[n][];i++)
for(j=;j<=ct[n-][];j++)
ans = max(ans,f[n][i][j]);
}
printf("%d\n",ans);
return ;
}
由于M很小，最多为10，所以可以对行进行状态压缩。二进制对应位为1表示放炮兵，为0表示空。我们可以事先生成所有有效的状态，即二进制数任何两个1都要相差两位以上，同时用数组记下此状态有多少个炮兵。对于地形也进行状态压缩，用1表求高地，0表示平原。判断某个状态能否放到某个地形，就是地形状态为1的地方，放置炮兵状态一定为0，这点可以用位运算解决。判断两个状态能否放在相邻行与此相同。
代码如下：
# include <iostream>
using namespace std; const int G = ;
const int N =;
const int M =; int d[][G][G];//滚动数组
int ph[N],f[G];//ph数组用于判断状态在第i行是否满足在P的平原设置，f数组则存放满足的状态
int n,m,g;//g为所有状态数 int OneC(int x){//计算x二进制1的个数，这个算法很优秀，是在《编程之美》书中学到的。
int t =;
while(x){
t ++;
x &= (x-);
}
return t;
}
void DP(){//dp
for(int k =; k < n ;k++){
for(int i =; i< g; i++){
if(ph[k] != (ph[k] | f[i]))continue;//判断状态f[i]是否满足在平原设置炮台
for(int j = ;j < g; j++){
if(ph[k-] != (ph[k-] | f[j]))continue;
if(f[i] & f[j])continue;//判断第k行和第k-1行的炮台是否有彼此击中
for(int q=; q< g; q ++){
if(ph[k-] != (ph[k-] | f[q]))continue;
if(f[q] & f[j])continue;
if(f[i] & f[q])continue;
d[k%][i][j] = max(d[k%][i][j], d[(k+)%][j][q] + OneC(f[i])); //状态方程
}
}
}
}
}
int main(){
scanf("%d %d",&n,&m);
int i ,j;
char ch[M];
for(i =;i < n; i++){//计算ph[]
ph[i] =;
scanf("%s", ch);
for(j =; j < m; j++){
if(ch[j] == 'P')
ph[i] += (<<(m-j-));
}
}
int v = <<m;
for(i =,g =; i< v;i++){//挑选合法状态
if(((i & (i << )) == ) && (i & (i <<))==)//这个想法不错哦。
f[g++] = i;
}
int pMax ;
if(n ==){
pMax = ;
for(i =; i<g ; i++){
if((ph[] | f[i])==ph[])
pMax = max( pMax , OneC(f[i]));
}
printf("%d" ,pMax);
return ;
}
memset(d, ,sizeof(d));
pMax = ;
for(i =; i < g; i++){//初始化d
if(ph[] != (ph[] | f[i]))continue;
for(j = ;j < g; j++){
if(ph[] != (ph[] | f[j]))continue;
if((f[i] & f[j]) ==){
d[][i][j] = OneC(f[i]) + OneC(f[j]);
pMax = max (pMax , d[][i][j]);
}
}
}
if(n ==){
printf("%d" ,pMax);
return ;
}
DP();
for(i =; i < g; i ++){
for(j =; j< g; j++){
pMax = max( pMax ,d[(n+)%][i][j]);
}
}
printf("%d", pMax);
return ;
}
代码如下：
# include<cstdio>
# include<string>
# include<cstring>
# include<iostream>
# include<cmath>
# include<algorithm>
using namespace std;
int n,m,sum,num,sta[<<],cot[<<],dp[][][],a[];
bool fit(int x,int y)
{
if(x&y)
return ;
return ;
}
void init()
{
sum=<<m;num=;
for(int i=;i<sum;i++)
{
if(i&(i<<)||i&(i<<))
continue;
sta[num]=i;
int temp = i,count=;
while(temp)
{
count++;
temp&=temp-;
}
cot[num++]=count;
}
}
void DP()
{
int ans=;
for(int i=;i<num;i++)
{
if(!fit(a[],sta[i]))
continue;
dp[][][i] = cot[i];
if(ans<dp[][][i])
ans=dp[][][i];
}
for(int i=;i<=n;i++)
for(int j=;j<num;j++)
for(int k=;k<num;k++)
{
if(!fit(sta[k],sta[j])||!fit(a[i],sta[k])||!fit(a[i-],sta[j]))
continue;
for(int l=;l<num;l++)
{
if(!fit(sta[k],sta[l])||!fit(sta[j],sta[l])||!fit(a[i-],sta[l])||!dp[i-][l][j])
continue;
dp[i][j][k]=max(dp[i][j][k],dp[i-][l][j]+cot[k]);
if(ans<dp[i][j][k])
ans=dp[i][j][k];
}
}
printf("%d\n",ans);
}
int main()
{
char s;
scanf("%d%d",&n,&m);
getchar();
init();
for(int i=;i<=n;i++)
{
for(int j=;j<=m;j++)
{
scanf("%c",&s);
if(s=='H')
{
int tem=<<(j-);
a[i]+=tem;
}
}
getchar();
}
DP();
return ;
}
另附转的一篇http://www.cnblogs.com/acm-bingzi/p/3278901.html