题目链接：http://poj.org/problem?id=1185
题意：
给 N，M（N<=100，M<=10），之后给出一个 N*M 由 "H"、"P" 组成的一个矩阵，H--代表山地，P--代表平原，一架炮的攻击范围如图所示；炮可以攻击 H（山地），但只能架在P（平原），在防止误伤的前提下（即炮不可以架在攻击范围之内，但攻击范围可以重叠），求整个区域最多能摆多少架炮？不是求方案数，不是求方案数，不是求方案数。
思路：
1.仔细分析问题后，发现该问题可以抽象为 0 1 的子问题，即假设 1 为有炮，0 为没有炮，最终答案是一个 N*M 的0 1矩阵中1的个数。
既然如此，先将N*M的H，P矩阵转换为01矩阵，再将其按行压缩为十进制的一维数组保。代码如下
char c;
for(int i=1;i<=N;++i)
{
int Sum=0;
for(int j=M-1;j>=0;--j)
{
cin>>c;
if(c=='P')
Sum+=(1<<j);//这里是位运算，如果不会参考我的上一篇博客，进行运算是括号括起来，再做为整体进行运算
}
a[i]=Sum;
}
2.再进行防止误伤的分析时，将每一个炮分为横向防止误伤，纵向防止误伤两种情况来处理。对横向防误伤可以进行预处理，只将不会进行相互攻击的情况提前找出来（即找出两个1之间有两个即两个以上0的情况）， 再看条件M<=10，最多有1024中 0 1的全排列，所以符合的状态最多有60种。代码如下
init(0,0);//main()中的接口
//普通递归函数求符合解，并保存
void init(int i,int flag)
{
if(i==M)
{
sta[sum]=0;//sta[]为保存符合的状态
sta_n[sum]=0;//sta_n[]为保存符合状态中1的个数
int n=0;
for(int i=0;i<M;++i)
{
if(num[i])//num[]为递归保存的01状态数组
{
++n;
sta[sum]+=(1<<i);
}
}
sta_n[sum]=n;
++sum;//符合状态总数
}
else
{
if(flag==0)//flag为之前1的距离
{
num[i]=0;
init(i+1,0);
num[i]=1;
init(i+1,2);
}
else
{
num[i]=0;
init(i+1,flag-1);
}
}
}
3.对于处理纵向防误伤，由状态转移方程处理：dp[i][j][k]=max(dp[i][j][k],dp[i-1][k][p]+sta_n[j]);（就是把第 i 行前两行（因为当且仅当第 i 行的前两行会影响第 i 行）的所有状态枚举出来，求出最值）
dp[i][j][k]：表示第 i 行，第 j 种状态在第 i-1 行是第 k 种状态的情况下最多的炮台数目；第1行和第2行另行处理；最大值不一定是在第 N 行出现（不是求方案数，所以要求全体最值）。代码如下
int ans=0;
if(N>=1)
{
for(int j=0;j<sum;++j)
{
if((sta[j]|a[1])==a[1])//如不理解此处含义，请翻上篇博客
for(int k=0;k<sum;++k)
{
dp[1][j][k]=sta_n[j];
ans=max(ans,dp[1][j][k]);
}
}
}
if(N>=2)
{
for(int j=0;j<sum;++j)
{
if((sta[j]|a[2])==a[2])
for(int k=0;k<sum;++k)
{
if((sta[k]&sta[j])==0)
{
dp[2][j][k]=dp[1][k][0]+sta_n[j];
ans=max(ans,dp[2][j][k]);
}
}
}
}
for(int i=3;i<=N;++i)
{
for(int j=0;j<sum;++j)
{
if((sta[j]|a[i])==a[i])
for(int k=0;k<sum;++k)
{
if((sta[j]&sta[k])==0)
for(int p=0;p<sum;++p)
{
if((sta[j]&sta[p])==0)
{
dp[i][j][k]=max(dp[i][j][k],dp[i-1][k][p]+sta_n[j]);
ans=max(ans,dp[i][j][k]);
}
}
}
}
}
AC代码：
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int num[20],sum=0,sta[65],sta_n[65];
int a[110],dp[110][65][65];
int N,M;
void init(int i,int flag)
{
if(i==M)
{
sta[sum]=0;
sta_n[sum]=0;
int n=0;
for(int i=0;i<M;++i)
{
if(num[i])
{
++n;
sta[sum]+=(1<<i);
}
}
sta_n[sum]=n;
++sum;
}
else
{
if(flag==0)
{
num[i]=0;
init(i+1,0);
num[i]=1;
init(i+1,2);
}
else
{
num[i]=0;
init(i+1,flag-1);
}
}
}
int main()
{
char c;
cin>>N>>M;
init(0,0);
for(int i=1;i<=N;++i)
{
int Sum=0;
for(int j=M-1;j>=0;--j)
{
cin>>c;
if(c=='P')
Sum+=(1<<j);
}
a[i]=Sum;
}
int ans=0;
if(N>=1)
{
for(int j=0;j<sum;++j)
{
if((sta[j]|a[1])==a[1])
for(int k=0;k<sum;++k)
{
dp[1][j][k]=sta_n[j];
ans=max(ans,dp[1][j][k]);
}
}
}
if(N>=2)
{
for(int j=0;j<sum;++j)
{
if((sta[j]|a[2])==a[2])
for(int k=0;k<sum;++k)
{
if((sta[k]&sta[j])==0)
{
dp[2][j][k]=dp[1][k][0]+sta_n[j];
ans=max(ans,dp[2][j][k]);
}
}
}
}
for(int i=3;i<=N;++i)
{
for(int j=0;j<sum;++j)
{
if((sta[j]|a[i])==a[i])
for(int k=0;k<sum;++k)
{
if((sta[j]&sta[k])==0)
for(int p=0;p<sum;++p)
{
if((sta[j]&sta[p])==0)
{
dp[i][j][k]=max(dp[i][j][k],dp[i-1][k][p]+sta_n[j]);
ans=max(ans,dp[i][j][k]);
}
}
}
}
}
printf("%d
",ans);
return 0;
}