炮兵阵地

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 2183 字
N行M列网格，P可部署、H不可；炮兵横向左右
一本通
练习
正文

/*
原题：T1595 「一本通 5.4 练习 2」炮兵阵地 (NOI 2001)
题意：N 行 M 列(M≤10)网格，P 可部署、H 不可；炮兵横向左右各 2、纵向上下各 2 受击；求最多部署数。
思路：行状压。单行合法状态 s：只落在 P 上，且任意两个 1 距离 ≥3（s&(s<<1)==0 且 s&(s<<2)==0）。
     用 dp[本行状态][上一行状态] 记录前 i 行最大炮兵数；新行 u 需与上一行 s、上两行 t 均不共列：u&(s|t)==0。
复杂度：时间 O(N·S³)，空间 O(S²)，S 为合法单行状态数（M=10 时 S≤60）。
易错点：1) 攻击范围是 2 格（非相邻），故需检查错位 1 与 错位 2；
       2) 需同时与“上一行”和“上两行”无冲突；3) 山地 H 上不可部署。
*/
#include <bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N,M;
    if(!(cin>>N>>M)) return 0;
    vector<int> plain(N,0);
    for(int i=0;i<N;i++){
        string s; cin>>s;
        for(int j=0;j<M;j++) if(s[j]=='P') plain[i]|=(1<<j);
    }
    // 对每一行，找出所有合法状态（落在 P 上且两两相距 ≥3）
    vector<vector<int>> rowSt(N), rowCnt(N);
    for(int i=0;i<N;i++){
        for(int s=0;s<(1<<M);s++){
            if((s&plain[i])!=s) continue;
            if((s&(s<<1))!=0) continue;
            if((s&(s<<2))!=0) continue;
            rowSt[i].push_back(s);
            rowCnt[i].push_back(__builtin_popcount(s));
        }
    }
    int S0=rowSt[0].size();
    // dp[b][c]：处理完“当前行”后，当前行状态 b、上一行状态掩码 c（c=0 表示无）的最大炮兵数
    vector<vector<int>> dp(S0,vector<int>(1,-1));
    for(int b=0;b<S0;b++) dp[b][0]=rowCnt[0][b];
    vector<int> ppMasks={0}; // 上两行的状态掩码列表，初始为“无”
    for(int i=1;i<N;i++){
        int Si=rowSt[i].size();
        int Sp=rowSt[i-1].size();
        vector<vector<int>> nd(Si,vector<int>(Sp,-1));
        for(int a=0;a<Si;a++){
            int ma=rowSt[i][a];
            int ca=rowCnt[i][a];
            for(int b=0;b<Sp;b++){
                int mb=rowSt[i-1][b];
                if((ma&mb)!=0) continue;
                for(int c=0;c<(int)ppMasks.size();c++){
                    if(dp[b][c]<0) continue;
                    int mc=ppMasks[c];
                    if((ma&mc)!=0) continue;
                    if(nd[a][b]<dp[b][c]+ca) nd[a][b]=dp[b][c]+ca;
                }
            }
        }
        dp=move(nd);
        ppMasks=rowSt[i-1]; // 下一轮的“上两行”即当前的上行
    }
    int ans=0;
    for(int b=0;b<(int)dp.size();b++)
        for(int c=0;c<(int)dp[b].size();c++)
            if(dp[b][c]>ans) ans=dp[b][c];
    cout<<ans<<"\n";
    return 0;
}
炮兵阵地

正文

一本通·提高篇的其它内容
