当前位置:编程学习 > C/C++ >>

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

补充:软件开发 , C++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,