萌新刚学状压 DP 求调，WA 30 pts

只 A 了 #1，#2，#9……

思路是先预处理所有合法状态，然后再 DP，不会爆空间。

#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;

const int N = 100 + 10;
const int SS = 200 + 10;
int n, m, f[N][SS][SS];
char g[N][15];
vector<int> st[N];

bool check1(int x, int S){
    for(int i=0;i<m;i++)
        if(((S >> i) & 1) && (g[x][i] == 'H'))
            return 0;
    for(int i=0;i<m-2;i++)
        if(((S >> i) & 1) && (((S >> (i + 1)) & 1) || ((S >> (i + 2)) & 1)))
            return 0;
    if(((S >> (m - 2)) & 1) && (((S >> (m - 1)) & 1)))
        return 0;
    return 1;
}

bool check2(int S1, int S2, int S3){
    for(int i=m-1;i>=0;i--)
        if(((S3 >> i) & 1) && (((S2 >> i) & 1) || ((S1 >> i) & 1)))
            return 0;
    return 1;
}

int main(){
    scanf("%d%d", &n, &m);
    for(int i=1;i<=n;i++)
        scanf("%s", g[i]);
    int all = (1 << m) - 1;

    for(int i=1;i<=n;i++){
        for(int S=0;S<=all;S++)
            if(check1(i, S))
                st[i].push_back(S);
    }
    for(int S: st[1])
        f[1][S][0] = __builtin_popcount(S);
    for(int S: st[2]){
        int d = __builtin_popcount(S);
        for(int S1: st[1])
            if(check2(0, S1, S))
                f[2][S][S1] = max(f[2][S][S1], f[1][S1][0] + d);
    }
    for(int i=3;i<=n;i++){
        for(int S: st[i]){
            int d = __builtin_popcount(S);
            for(int S1: st[i - 1]){
                for(int S2: st[i - 2]){
                    if(check2(S2, S1, S))
                        f[i][S][S1] = max(f[i][S][S1], f[i - 1][S1][S2] + d);
                }
            }
        }
    }
    int ans = 0;
    for(int S: st[n])
        for(int S1: st[n - 1])
            ans = max(ans, f[n][S][S1]);
    printf("%d\n", ans);
    return 0;
}