P2704 [NOI2001] 炮兵阵地——我不熟的状压

li_cat · 2025-05-31 14:05:48 · 个人记录

第一眼看，数据很状压（？）

然后发现每行每个节点的状态只有 0 或 1 ，考虑状压DP

dp本身

设状态 dp_{st_1,st_2,st_3,i} 为本行状态为 st_1 ,上一行状态为 st_2 ,上上行状态为 st_3 ,枚举到第 i 行时的可行性

这个状态定义的是非常差的，首先是空间开不下，其次存的是可行性，非常浪费

可以想到 st_3 直接通过枚举来转移，那么这里存的就是枚举到第 i 行，这一行状态为 st_1 和上一行状态为 st_2 时的最大放置数量

那么就可以很方便的进行转移了，就是枚举第三行的情况，然后从第 i-1 行转移到第 i 行

状态转移方程就是

dp_{st_1,st_2,i}=max(dp_{st_2,st_k,i-1}+cnt_{st_1})

此处 cnt_{st_1} 是指这一行炮兵的数量， st_k 是指所有合法的上上行的状态

合法性判定

左右 2 格内是否有炮兵可以采用位运算来判断，即将状态左移 1/2 格取与，如果各自两格以内没有炮兵就应该会恰好错开结果为 0 ，否则结果为 1
与上一行，上两行的冲突可以取与，相同位置都有炮兵就不会消掉，结果就不是 0 ，即非法为 1 合法为 0
与地形判定的话可以将地形转化为二进制串，然后取与，令不能放兵的位置为 1 ，然后和第二个道理一样
滚动数组

这样会爆空间

想了下，发现滚动数组的实现比以前写的简单不少，本来还挺不喜欢写滚动数组的

可以认为滚动数组是（需要）一种映射，只要保证在状态转移的过程中不会出现两个不同的映射到同一个位置就好

一般来说取模是最好用的方法

AC Code:

#include <bits/stdc++.h>

using namespace std;

const int MAXN=105;

int dp[(1<<11)][(1<<11)][3];

int cnt[(1<<11)];

int n,m;
string st;
int mapn[MAXN];//地图,1不能放,0可以放 

void init(int idx,int sit,int count){
    cnt[sit]=count;
    if(idx>m) return ;
    init(idx+1,sit,count);
    init(idx+1,sit|(1<<(idx-1)),count+1);
}//

void work(){
    scanf("%d%d",&n,&m);
    init(1,0,0);
    for(int i=1;i<=n;++i){
        cin>>st;
        for(int j=0;j<m;++j)
            if(st[j]=='H') mapn[i]|=(1<<j);
    } 

    for(int i=0;i<(1<<m);++i)
        if(!(mapn[1]&i || ((i<<2)&i) || ((i<<1)&i)))
            dp[i][0][1]=cnt[i];

    for(int i=0;i<(1<<m);++i)
        if(!(mapn[1]&i || ((i<<2)&i) || ((i<<1)&i)))
            for(int j=0;j<(1<<m);++j)
                if(!(i&j || mapn[2]&j || ((j<<2)&j) || ((j<<1)&j)))
                    dp[j][i][2]=cnt[i]+cnt[j];

    for(int i=3;i<=n;++i){
        for(int j=0;j<(1<<m);++j){//枚举这一行 
            if(mapn[i]&j || ((j<<2)&j) || ((j<<1)&j)) continue;
            for(int k=0;k<(1<<m);++k){//枚举上一行 
                if(mapn[i-1]&k || ((k<<2)&k) || ((k<<1)&k)) continue;
                if(j&k) continue;
                for(int l=0;l<(1<<m);++l){//枚举上上行 
                    if(mapn[i-2]&l || ((l<<2)&l) || ((l<<1)&l)) continue;
                    if(l&j || l&k) continue;
                    dp[j][k][i%3]=max(dp[j][k][i%3],dp[k][l][(i-1)%3]+cnt[j]);
                }
            }
        }
    }
    int res=0;
    for(int i=0;i<(1<<m);++i)
        for(int j=0;j<(1<<m);++j)
            res=max(res,dp[i][j][n%3]);
    printf("%d",res);
}

int main(){
    work();
    return 0;
}