wa80pt

对模板打的

#include<bits/stdc++.h>
using namespace std;
int dp[2025][2025][12];
char ch[2025][2025];
int a[2025];
int SUM[2025];
int n, m;
int getsum(int index) {
    int tot = 0;
    while(index) {
        if(index & 1) {
            tot++;
        }
        index /= 2;
    }
    return tot;
}
int main() {
    cin >> n >> m;
    for(int i=0; i<n; ++i) {
        for(int j=0; j<m; ++j) {
            cin >> ch[i][j];
            if(ch[i][j] == 'H') {
                a[i] = a[i] << 1;
                a[i] += 1;
            } else {
                a[i] <<= 1;
            }
        }
    }
    for(int i=0; i<(1<<m); ++i) {
        SUM[i] = getsum(i);
    }
    for(int i=0; i<(1<<m); ++i) {
        if(!((i & a[0]) || (i & (i<<1)) || (i & (i << 2)))) {
            dp[0][i][0] = SUM[i];
        }
    }
    for(int i=0; i<(1<<m); ++i) {
        for(int j=0; j<(1<<m); ++j) {
            if(!(i & j || i & a[0] || j & a[0] || i & (i << 2) || j & (j << 2) || i & (i << 1) || j & (j << 1))) {
                dp[i][j][1] = SUM[i] + SUM[j];
            }
        }
    }
    for(int i=2; i<n; ++i) {
        for(int j=0; j<(1<<m); ++j) {
            if(j&a[i-1] || (j&(j<<1)) || (j&(j<<2))) {
                continue;
            }
            for(int k=0; k<(1<<m); ++k) {
                if(k&a[i] || (k&(k<<1)) || (k&(k<<2)) || k & j) {
                    continue;
                }
                for(int l=0; l<(1<<m); ++l) {
                    if(l&a[i-2] || (l&(l<<1)) || (l&(l<<2)) || l & k || l & j) {
                        continue;
                    }
                    dp[j][k][i%3]=max(dp[j][k][i%3],dp[l][j][(i-1)%3]+SUM[k]);
                }
            }
        }
    }
    int ans = 0;
    for(int i=0;i<(1<<m);i++)
        for(int j=0;j<(1<<m);j++)
            ans=max(ans,dp[i][j][(n-1)%3]);
    cout << ans;
    return 0;
}