P2704 炮兵阵地

phmaprostrate · 2021-11-12 20:58:24 · 个人记录

分析

一看就是状压DP,别问我为啥。这次的状压比较猛，它需要考虑 3 层，所以要考虑设计 3 层状态。

设计 dp[i][j][k] 为第 i 层状态为 j 上一层状态为 k 的所放的棋子数。之前需要预处理前一行，这次为前两行。同时，枚举时也为 4 层循环。空间有限制，要用滚动数组。与其他 DP 题同理，有地图上的限制，有 Map[i] 来存第 i 种状态。还有 so[i] 表示第 i 种状态能摆放的炮兵数量。

这样我们就可以可以开心的预处理了。

1.预处理第一层状态，有其他状压类似，i << 1 & i 判断相邻位以为是否都有 1，此题有相邻两位的限制需加上 i << 2 & i 预处理完后，同理预处理第 2 行。限制条件有：

1.状态本身合法。

2.不与第 1 行冲突，没有第零行（雾

3.不与地图冲突，(放山地啊？

最后，运算时，分别枚举 i,j,s,u 分别表示行数，该行状态，上一行状态，上上行状态。转移方程式显然。

#include<iostream>
using namespace std;
const int N = 102,M = 11,S = 1 << M;
int so[S];
int Map[N];
bool can[S];
bool check(int ss){
    if((((ss << 1) & ss) == 0) &&(((ss << 2) & ss) == 0)) return true;
    else return false;
}
int n,m;
int dp[2][S][S];
int main(){
    cin >> n >>m;
    for(int i = 1;i <= n;i++){
     for(int j = 1;j <= m;j++){
        char x; 
        cin >> x;
        Map[i] = (Map[i] << 1) + ( x == 'P');
     }
    }
     int statem = (1 << m) - 1;
     for(int i = 0;i <= statem;i++){
        int x = i;
        while(x){
        so[i]++;
         x = (x - 1) & x;   
         }
     }

     for(int i = 0;i <= statem;i++){
        if(check(i)) can[i] = true;
     }
     for(int i = 0;i <= statem;i++){
        if(can[i] && ((Map[1] & i) == i)) dp[0][0][i] = so[i];
     }
     for(int i = 0;i <= statem;i++){
        if(can[i]){
            for(int j = 0;j <= statem;j++){
                if(!can[j] || (i & j) || ((Map[2] & j) != j)) continue;
                dp[1][i][j] = max(dp[0][0][i] + so[j],dp[1][i][j]);
             }
         }
     }
     int flag  = 0;
     for(int i = 3;i <= n ;i++){
      for(int j = 0;j <= statem;j++){
        if(can[j] && ((Map[i] & j) == j)){
            for(int s = 0;s <= statem;s++){
                if(!can[s]) continue;
                for(int u = 0;u <= statem;u++){
                    if(!can[u] || (u & s) || (u & j) || (j & s)) continue;
                    dp[flag][s][j] = max(dp[flag][s][j],dp[flag ^ 1][s] + so[j]);
                  }
              }
          }
      }
      flag = flag ^ 1;
    }
      int ans = 0;
      for(int u = 0;u <= statem;u++){
       for(int j = 0;j <= statem;j++){
        ans = max(ans,dp[flag ^ 1][u][j]);
       }
    }
       cout<<ans;
    return 0;
}