新人初学状压 DP 20分求助

RT，感觉很玄学……

#include <algorithm>
#include <cstring>
#include <iostream>
#include <cstdio>
#include <vector>
#include <cctype>
#include <cmath>
#include <unordered_map>
#define ll long long
#define ri register int
using namespace std;

char buf[1 << 20], *p1, *p2;
//#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2)?EOF: *p1++)
template <typename T> inline void read(T &t) {
    ri v = getchar();T f = 1;t = 0;
    while (!isdigit(v)) {if (v == '-')f = -1;v = getchar();}
    while (isdigit(v)) {t = t * 10 + v - 48;v = getchar();}
    t *= f;
}
template <typename T,typename... Args> inline void read(T &t,Args&... args) {
    read(t);read(args...);
}

const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3fLL;
const int N = 101;
const int M = 11;

int f[N][1<<M][1<<M],s[1<<M],n,m,a[N],tot;

inline bool check(int x) {
    if (x & (x << 1)) return false;
    if (x & (x << 2)) return false;
    if (x & (x >> 1)) return false;
    if (x & (x >> 2)) return false;
    return true;
}

inline int count(int x) {
    int ans = 0;
    while (x) {
        if (x & 1) ++ans;
        x >>= 1;
    }
    return ans;
}

int main() {
    cin >> n >> m;
    for (int i = 1;i <= n;++i) {
        int p = 0;
        for (int j = 1;j <= m;++j) {
            char s;cin >> s;
            if (s == 'H') p = (p << 1)+ 1;
            else p <<= 1;
        }
        a[i] = p;
    }
    for (int i = 0;i < 1 << m;++i) {
        if (check(i)) s[++tot] = i;
    }
    for (int i = 1;i <= tot;++i) {
        if ((s[i] & a[1]) == 0) {
            f[1][i][0] = count(s[i]);
        }
    } 
    for (int i = 1;i <= tot;++i) {
        if ((s[i] & a[2])== 0) {
            for (int j = 1;j <= tot;++j) {
                if ((s[j] & a[1])== 0 && (s[i] & s[j])== 0) {
                    f[2][i][j] = count(s[i]) + count(s[j]);
                }
            }
        }
    }
    for (int i = 3;i <= n;++i) {
        for (int j = 1;j <= tot;++j) {
            int x = s[j];
            if ((x & a[i]) == 0){
                for (int k = 1;k <= tot;++k) {
                    int y = s[k];
                    if ((y & a[i-1] )== 0 && (x & y) == 0 ){
                        for (int l = 1;l <= tot;++l) {
                            int z = s[l];
                            if ((y & z) == 0 && (z & a[i-2]) == 0 && (x & z) == 0) {
                                f[i][x][y] = max(f[i][x][y],f[i-1][y][z] + count(x));
                            }
                        }
                    }
                }
            }
        }
    }
    int ans = 0;
    for (int i = 1;i <= tot;++i) {
        for (int j = 1;j <= tot;++j) {
            ans = max(ans,f[n][i][j]);
        }
    }
    printf("%d",ans);
    return 0;
}