题意：

给出一个n*m的矩阵，矩阵的每个方格标有P/H p表示可以安置大炮，H表示不能安置大炮，当大炮安置于(i,j)点时，其左右两个单位以及上下两个单位都在攻击范围，求在两支大炮不会相互攻击的前提下，最多能够安置大炮的数量。

思路：

当前行大炮的的安置要受其前两行的影响，所以状态转移方程有：

dp[i][j][k] = max(dp[i][j][k],dp[i - 1][k][l] + sum[j])   dp[i][j][k]表示第i行的状态为j第i - 1的状态为k    sum[j]表示该行取j状态时可能增加的数量；

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #define CL(a,num) memset(a,num,sizeof(a))#define M 13#define N 107#define MOD 100000000using namespace std;const int inf = 1999999;int map[N],dp[N][66][66];int state[1<
           
             0)//有多少个1就能增加多少 { if (x&1) s++; x>>=1; } return s;}void init(){ int i; ct = 0; for (i = 0; i < total; ++i) { if (isok(i))//枚举所有可能状态 { state[ct] = i; sum[ct++] = getsum(i);//求出该状态下能够添加的大炮的数量 } }}int main(){ //freopen("din.txt","r",stdin); int i,j,k,l; scanf("%d%d",&n,&m); CL(map,0); CL(sum,0); for (i = 0; i < n; ++i) { scanf("%s",str[i]); for (j = 0; j < m; ++j) { if (str[i][j] == 'H') map[i] |= (1<
            
             = 2)//大于两行时 { for (l = 0; l < ct; ++l) { if (!(map[i - 2]&state[l]) && !(state[j]&state[l]) && !(state[k]&state[l]))//i,i - 1,i - 2都要满足条件 { dp[i][j][k] = max(dp[i][j][k],dp[i - 1][k][l] + sum[j]); } } } else dp[i][j][k] = max(dp[i][j][k],dp[i - 1][k][0] + sum[j]); } } } } } int ans = 0; for (i = 0; i < ct; ++i) { for (j = 0; j < ct; ++j) { ans = max(ans,dp[n - 1][i][j]); } } printf("%d\n",ans); return 0;}