POJ1185 炮兵阵地（Jan. 27th, 2019） 状压DP

//  La Pluie Froid
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 100 + 3, M = 70 + 3;
int p[N], n, m, dp[N][M][M], pluie[M], cal[M], t;
char s[15];
int Cal(int x){
    int res = 0;
    while(x){
        if(x & 1) res++;
        x >>= 1;
    }
    return res;
}
void Geography(){
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= n; i ++){
        scanf("%s", s + 1);
        for(int j = 1; j <= m; j++){
            p[i] |= (s[j] == 'H') << (j - 1);
        }
    }
}
void Legal(){
    for(int i = 0; i < (1 << m); i ++){
        if((i & (i << 1)) || (i & (i << 2))) continue;
        pluie[++ t] = i;
    }
    for(int i = 1; i <= t; i ++){
        if(p[1] & pluie[i]) continue;
        dp[1][i][1] = Cal(pluie[i]); // 此处第三维的含义是：第i-1行全为0的情况在pluie数组中坐标为1。 
    }
}
int main(){
    Geography();
    memset(dp, -1, sizeof(dp));
    Legal();
    for(int i = 2; i <= n; i ++){
        for(int j = 1; j <= t; j ++){
            if(pluie[j] & p[i]) continue;
            for(int k = 1; k <= t; k ++){
                if(pluie[k] & p[i - 1]) continue;
                if(pluie[j] & pluie[k]) continue;
                for(int l = 1; l <= t; l ++){
                    if(pluie[l] & p[i - 2]) continue;
                    if(pluie[j] & pluie[l]) continue;
                    if(pluie[k] & pluie[l]) continue;
                    if(dp[i - 1][k][l] == -1) continue;
                    dp[i][j][k] = max(dp[i][j][k], dp[i - 1][k][l] + Cal(pluie[j]));
                }
            }
        }
    }
    int ans = 0;
    for(int i = 1; i <= t; i++){
        for(int j = 1; j <= t; j++){
            ans = max(ans, dp[n][i][j]);
        }
    }
    printf("%d", ans);
    return 0;
}