E27 状态压缩DP 炮兵部队

#include <bits/stdc++.h> //by:hansang.Venezia
using namespace std;
const int N=110, M=10, K=(1<<M)+10;
char s[N][M]; int dp[2][K][K], n, m;
//dp[i][j][k]表示当前在第i行，状态为j，上一行状态为k
//状态是一个二进制数，其中这个位置是1就代表着这个位置放了炮弹
//数组要滚动，不然有点悬
int calc(int x){ //求二进制数里面有几个1
    int res=0;
    for(int i=x; i>=1; i-=i&-i) res++;
    return res;
}
bool pd1(int x){ //检测x是否有相连或相隔一个位置的1
    if((x&(x<<1)) || (x&(x<<2))) return 0;
    else if((x&(x>>1)) || (x&(x>>2))) return 0;
    else return 1;
}
bool pd2(int x, int i){ //检测x中为1的位置是不是H（炮兵部队不能放在山上
    bool flag=1;
    for(int j=1; j<=m; j++) if((1<<(j-1))&x){
        if(s[i][j]=='H') {flag=0; break;}
    }
    return flag;
}
int main(){
    scanf("%d%d", &n, &m);
    for(int i=1; i<=n; i++) scanf("%s", s[i]+1);
    memset(dp, 0, sizeof(dp));
    for(int i=0; i<(1<<m); i++) if(pd1(i) && pd2(i, 1)){
        dp[1][i][0]=calc(i); //1的情况不受限制，特殊处理
    }
    int t=1, ans=0;
    for(int i=2; i<=n; i++){
        t^=1; //滚动
        for(int now=0; now<(1<<m); now++) if(pd1(now) && pd2(now, i)){
            int x=calc(now);                        //当前状态now合法
            for(int l2=0; l2<(1<<m); l2++) if(pd1(l2) && (!(l2&now))){
                for(int l1=0; l1<(1<<m); l1++) if(pd1(l1) && (!(l1&now)) && (!(l2&l1))){
                    dp[t][now][l1]=max(dp[t][now][l1], dp[t^1][l1][l2]+x);
                    //当前状态为上一行合法的状态值加上当前行放了多少炮弹部队
                    //(l1和l2不用pd2的原因是不合法的状态之前循环时一定没有赋值
                }
            }
        }
    }
    for(int l1=0; l1<(1<<m); l1++) if(pd1(l1)){
        for(int l2=0; l2<(1<<m); l2++) if(pd1(l2) && (!(l2&l1))){
            ans=max(ans, dp[t][l1][l2]);
            //第n行的合法状态
        }
    }
    printf("%d\n", ans);
    return 0;
}

E27 状态压缩DP 炮兵部队E27 状态压缩DP 炮兵部队

#include<bits/stdc++.h> //by:hansang.Venezia
using namespace std;
const int N=110, M=10, K=(1<<M)+10;
char s[N][M]; int dp[2][K][K], n, m;
//dp[i][j][k]表示当前在第i行，状态为j，上一行状态为k
//状态是一个二进制数，其中这个位置是1就代表着这个位置放了炮弹
//数组要滚动，不然有点悬
int calc(int x){ //求二进制数里面有几个1
    int res=0;
    for(int i=x; i>=1; i-=i&-i) res++;
    return res;
}
bool pd1(int x){ //检测x是否有相连或相隔一个位置的1
    if((x&(x<<1)) || (x&(x<<2))) return 0;
    else if((x&(x>>1)) || (x&(x>>2))) return 0;
    else return 1;
}
bool pd2(int x, int i){ //检测x中为1的位置是不是H（炮兵部队不能放在山上
    bool flag=1;
    for(int j=1; j<=m; j++) if((1<<(j-1))&x){
        if(s[i][j]=='H') {flag=0; break;}
    }
    return flag;
}
int main(){
    scanf("%d%d", &n, &m);
    for(int i=1; i<=n; i++) scanf("%s", s[i]+1);
    memset(dp, 0, sizeof(dp));
    for(int i=0; i<(1<<m); i++) if(pd1(i) && pd2(i, 1)){
        dp[1][i][0]=calc(i); //1的情况不受限制，特殊处理
    }
    int t=1, ans=0;
    for(int i=2; i<=n; i++){
        t^=1; //滚动
        for(int now=0; now<(1<<m); now++) if(pd1(now) && pd2(now, i)){
            int x=calc(now);                        //当前状态now合法
            for(int l2=0; l2<(1<<m); l2++) if(pd1(l2) && (!(l2&now))){
                for(int l1=0; l1<(1<<m); l1++) if(pd1(l1) && (!(l1&now)) && (!(l2&l1))){
                    dp[t][now][l1]=max(dp[t][now][l1], dp[t^1][l1][l2]+x);
                    //当前状态为上一行合法的状态值加上当前行放了多少炮弹部队
                    //(l1和l2不用pd2的原因是不合法的状态之前循环时一定没有赋值
                }
            }
        }
    }
    for(int l1=0; l1<(1<<m); l1++) if(pd1(l1)){
        for(int l2=0; l2<(1<<m); l2++) if(pd1(l2) && (!(l2&l1))){
            ans=max(ans, dp[t][l1][l2]);
            //第n行的合法状态
        }
    }
    printf("%d\n", ans);
    return 0;
}