題意：中文題意，，，
思路：題目給的是一個n*m的矩陣，其中有一些方格不能放炮彈，而且每枚炮彈的攻擊范圍是2，也就是說，若一個方格放置了炮彈，則該方格上下左右的2個方格都不能放炮彈。我們一行一行來考慮，由於m的范圍比較小（<= 10），所以我們可以先用dfs枚舉出來每行可能放炮彈的狀態，然後再想，因為炮彈的攻擊范圍是2，所以第i行炮彈放置的情況和第i-1行以及第i-2行的放置情況有關。用數組dp[i][j][k]表示第i行的第j個狀態和第i-1的第j個狀態時，前i行最多能放多少個炮彈。則dp[i][j][k] = max(dp[i-1][j][z] + numbomb[i][j]),其中numbomb[i][j]表示第i行是第j個狀態時，可以放置炮彈的數量，而且要保證第i行的第j個狀態以及第i-1行的第k個狀態以及第i-2行的第z個狀態不沖突。
其中，我們需要用數組記錄下來每行的每一個狀態和該狀態的炮彈數量，以及狀態的數量和狀態與狀態之間是否沖突的情況。實現比較復雜，代碼寫了100+，而且寫了一天，，，第一道狀態壓縮。
代碼：
[cpp]
#include <iostream>
#include <cstdio>
#include <string.h>
#include <string>
using namespace std;
#define CLR(arr,val) memset(arr,val,sizeof(arr))
char ss[110][15];
int n,m,flag[15],sum[110],cnt,numbomb[110][100],one_zero[100][100][15],numzt[110];
int dp[110][110][110],ans[110],mm,cross[110][2][70][70];
void init(){
CLR(sum,0);
CLR(flag,0);
CLR(numbomb,0);
CLR(one_zero,0);
CLR(numzt,0);//每一行狀態的數量
CLR(dp,0);
CLR(ans,0);
CLR(cross,0);
mm = 0;
}
void give_value(int row){
for(int i = 0;i < m;++i){
if(flag[i]){
numbomb[row][numzt[row]]++;
}
}
for(int i = 0;i < m;++i){
one_zero[row][numzt[row]][i] = flag[i];
}
numzt[row]++;
}
void dfs(int row,int id){
for(int i = 0;i < m;++i){
if(ss[row][i] == 'P' && !flag[i] && i - id > 2){
flag[i] = 1;
dfs(row,i);
flag[i] = 0;
}
}
give_value(row);
}
void fun(int x){
bool isP = false;
for(int i = 0;i < m;++i){
CLR(flag,0);
if(ss[x][i] == 'P'){
cnt = 1;
isP = true;
flag[i] = 1;
dfs(x,i);
}
}
if(!isP)
numzt[x] = 65;
}
bool cmp(int up,int upid,int up_up,int up_upid){
CLR(ans,0);
for(int i = m-1;i >= 0;--i){
ans[i] = one_zero[up][upid][i] & one_zero[up_up][up_upid][i];
}
for(int i = m-1;i >= 0;--i){
if(ans[i] == 1)
return false;
}
return true;
}
void yuchuli(){
for(int i = 0;i < numzt[0];++i){
for(int j = 0;j < numzt[0];++j){
dp[0][i][j] = numbomb[0][i];
if(mm < dp[0][i][j])
mm = dp[0][i][j];
}
}
for(int i = 0; i < numzt[1];++i){
for(int j = 0;j < numzt[0];++j){
if(cmp(1,i,0,j)){
dp[1][i][j] = max(dp[1][i][j],dp[0][j][j] + numbomb[1][i]);
if(mm < dp[1][i][j])
mm = dp[1][i][j];
}
}
}
for(int i = 0;i < numzt[1];++i){
for(int j = 0;j < numzt[0]; ++j){
if(cmp(1,i,0,j)){
cross[1][1][i][j] = 1;
}
}
}
for(int i = 2;i < n; ++i){
for(int numi = 0; numi < numzt[i];++numi){
for(int numj = 0; numj < numzt[i-1]; ++numj){
if(cmp(i,numi,i-1,numj))
cross[i][1][numi][numj] = 1;
}
for(int numj = 0; numj < numzt[i-2]; ++numj){
if(cmp(i,numi,i-2,numj))
cross[i][0][numi][numj] = 1;
}
}
}
}
int max(int a,int b){
return a>b?a:b;
}
int main(){
while(scanf("%d%d",&n,&m) != EOF){
init();
for(int i = 0;i < n;++i){
scanf("%s",ss[i]);
for(int j = 0;j < m;++j){
if(ss[i][j] == 'P')
sum[i]++;
}
}
for(int i = 0;i < n;++i){
fun(i);
}
yuchuli();
int mmax = 0,ans = 0;
for(int i = 2;i < n;++i){
int numi = 0,numj = 0,numk = 0;
for(numi = 0;numi < numzt[i];++numi){
for(numj = 0;numj < numzt[i-1];++numj){
mmax = 0;
for(numk = 0;numk < numzt[i-2];++numk){
if(cross[i][0][numi][numk] && cross[i][1][numi][numj] && cross[i-1][1][numj][numk]){
if(mmax < dp[i-1][numj][numk] + numbomb[i][numi]){
mmax = dp[i-1][numj][numk] + numbomb[i][numi];
}
}
}
dp[i][numi][numj] =max( mmax , dp[i-1][numj][numk]);
ans = max(ans,dp[i][numi][numj]);
}
}
}
printf("%d\n",max(ans,mm));
}
return 0;
}
