rt，WA#8#9 80pts

#8我的结果比答案少2

/*
Luogu P2704 炮兵阵地
https://www.luogu.com.cn/problem/P2704
*/
#include "iostream"
#include "cstring"
#include "vector"
using namespace std;
int hills[105];
int dp[2][1024][1024], ans;
int n, m;
vector<int>valid_rows;
int popcount(int u){
    int ret=0;
    while(u){
        u=(u&(u-1));
        ret++;
    }
    return ret;
}
int main(){
    cin >> n >> m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            char c;
            cin >> c;
            hills[i]=hills[i]*2+(c=='H');
        }
    }
    for(int i=0;i<(1<<m);i++){
        if((i<<1 & i) || (i<<2 & i) || (i>>1 & i) || (i>>2 & i)) continue;
        valid_rows.push_back(i);
    }
    for(int i:valid_rows){
        if(i&hills[0]) continue;
        dp[0][0][i]=popcount(i);
        ans=max(ans, dp[0][0][i]);
    }
    if(n==1){
        cout << ans;
        return 0;
    }
    for(int pre:valid_rows){
        if(pre&hills[0]) continue;
        for(int now:valid_rows){
            if(now&hills[1]) continue;
            if(pre&now) continue;
            dp[1][pre][now]=popcount(pre)+popcount(now);
            ans=max(ans, dp[1][pre][now]);
        }
    }
    if(n==2){
        cout << ans;
        return 0;
    }
    memset(dp[0], 0, sizeof(dp[0]));
    int NOW=0, PRE=1;
    for(int c=3;c<=n;c++){
        for(int now:valid_rows){
            if(now&hills[c]) continue;
            for(int pre1:valid_rows){
                if(pre1&hills[c-2]) continue;
                if(now&pre1) continue;
                for(int pre2:valid_rows){
                    if(pre2&hills[c-1]) continue;
                    if(now&pre2) continue;
                    dp[NOW][pre2][now]=max(dp[NOW][pre2][now], dp[PRE][pre1][pre2]+popcount(now));
                    if(c==n)
                        ans=max(ans, dp[NOW][pre2][now]);
                }
            }
        }
        memset(dp[PRE], 0, sizeof(dp[PRE]));
        swap(NOW, PRE);
    }
    cout << ans << "\n";
}