算法竞赛模板

状压DP

注意到每行只有10，可以用考虑状压，用状压后的1表示此处有炮兵
每放一个炮兵会影响下面两行，所以值要考虑当前行和前面两行的即可
f[i][j][k] 表示当前处理到第i行， 前一行是状态j的最大放置数量
然后可以通过f[i-1][j][k] 枚举所有前两行的状态，更新f[i][j][k]
注意预处理后本来1024^3 的状态数变成了 60^3
暴力枚举完全可以接受

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
// #define int ll

int hill[11];
int f[101][61][61];
int c[101][61];
int p[101];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    char ch;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> ch;
            if (ch == 'H') {
                hill[i] |= (1 << (m-j));
            }
        }
    }
    vector<int> ok;
    for (int i = 0; i < (1 << m); i++) {
        if ((i & (i << 1)) != 0 || (i & (i << 2)) != 0) {
            continue;
        }
        ok.push_back(i);
    }

    for (int i = 1; i <= n; i++) {
        int cnt = 0;
        for (auto j : ok) {
            if ((j & hill[i]) == 0) {
                c[i][++cnt] = j;
            }
        }
        p[i] = cnt;
    }

    if (n == 1) {
        int tot = 0;
        for (int i = 1; i <= p[1]; i++) {
            tot = max(tot,__popcount(c[1][i]));
        }
        cout << tot;
        return 0;
    }

    for (int i = 1; i <= p[2]; i++) {
        for (int j = 1; j <= p[1]; j++) {
            if ((c[2][i] & c[1][j]) != 0) {
                continue;
            }
            f[2][i][j] = __popcount(c[2][i]) + __popcount(c[1][j]);
        }
    }

    for (int i = 3; i <= n; i++) {
        for (int j = 1; j <= p[i]; j++) {
            for (int k = 1; k <= p[i-1]; k++) {
                for (int l = 1; l <= p[i-2]; l++) {
                    if ((c[i][j] & c[i-1][k]) || (c[i][j] & c[i-2][l])) {
                        continue;
                    }
                    f[i][j][k] = max(f[i][j][k],f[i-1][k][l] + __popcount(c[i][j]));
                }
            }
        }
    }
    
    int ans = 0;
    for (int i = 1; i <= p[n]; i++) {
        for (int j = 1; j <= p[n-1]; j++) {
            ans = max(ans,f[n][i][j]);
        }
    }
    cout << ans;
    return 0;
}