POJ 1185 炮兵阵地 状态压缩
题意：中文题意，，，
思路：题目给的是一个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;
}
