90pts，求助

Kobe303 @ 2022-03-03 18:16:46

by Kobe303 @ 2022-03-03 18:17:36

代码贴二楼，附第二个点的数据

#include <bits/stdc++.h>
using namespace std;
const int N = 105, M = 10;
int f[2][1<<M][1<<M];
int n, m;
int Count[1<<M];
bool valid[N][1<<M];
char s[N][M];
int sta[1<<M], cnt;

bool check(int x) {
    int lst = -2;
    for (int i = 1; i <= m; ++i) {
        if (x & 1) {
            if (i - lst < 3) return false;
            lst = i;
        }
        x >>= 1;
    }
    return true;
}

bool check2(int i, int x) {
    for (int j = 0; j < m; ++j) {
        if (x >> j & 1) {
            if (s[i][j] == 'H') return false;
        }
    }
    return true;
}

int calc(int x) {
    int res = 0;
    for (; x; x -= x & -x) ++res;
    return res;
}

int main() {
    memset(f, 0xcf, sizeof f);
    f[0][0][0] = 0;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) scanf("%s", s[i]);
    for (int i = 0; i < (1 << m); ++i)
        if (check(i)) sta[++cnt] = i, Count[i] = calc(i);
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= cnt; ++j) {
            if (check2(i, sta[j])) valid[i][sta[j]] = 1;
        }
    }
    for (int j = 1; j <= cnt; ++j) valid[0][sta[j]] = 1;
    for (int i = 1; i <= cnt; ++i) 
        for (int j = 1; j <= cnt; ++j) {
            if ((sta[i] & sta[j]) != 0) continue;
            f[1][sta[i]][sta[j]] = Count[sta[i]];
        }
    for (int i = 2; i <= n; ++i) {
        for (int j = 1; j <= cnt; ++j) {
            for (int k = 1; k <= cnt; ++k) {
                if (valid[i][sta[j]] && valid[i - 1][sta[k]] && ((sta[j] & sta[k]) == 0)) {
                    for (int l = 1; l <= cnt; ++l) {
                        if ((sta[j] & sta[l]) != 0) continue;
                        f[i & 1][sta[j]][sta[k]] = max(f[i & 1][sta[j]][sta[k]], f[(i - 1) & 1][sta[k]][sta[l]]);
                    }
                    f[i & 1][sta[j]][sta[k]] += Count[sta[j]];  
                }
            }
        }
    }
    int ans = 0;
    for (int j = 1; j <= cnt; ++j)
        for (int k = 1; k <= cnt; ++k) {
            if ((sta[j] & sta[k]) == 0 && valid[n][sta[j]] && valid[n - 1][sta[k]])
                ans = max(ans, f[n & 1][sta[j]][sta[k]]);
        }
    printf("%d", ans);
    return 0;
}
/*
8 4
HPPH
PPPP
HPPH
PHHP
PHHP
HPPH
PPPP
HPPH
*/
// 8

by Loser_King @ 2022-03-03 18:18:04

本来就是吧，因为每个炮可以向后影响两列

by Kobe303 @ 2022-03-03 18:18:22

这个是 90\text{pts} 代码

by Kobe303 @ 2022-03-03 18:18:59

@Loser_King 可是转移只跟上一行有关啊

by Kobe303 @ 2022-03-03 18:19:27

@Loser_King 老莽这样写就能过，是我写的太烂了

by moao @ 2022-03-03 18:20:33

@Kobe303 不懂为什么可以只滚2行

by Kobe303 @ 2022-03-03 18:21:01

@Golden_Breath 转移只跟上一行有关啊

by moao @ 2022-03-03 18:22:47

@Kobe303 这样难道不会出现不合法的状态吗

by Loser_King @ 2022-03-03 18:23:38

这样的话状态真的不用压成三进制么

by Kobe303 @ 2022-03-03 18:23:49

@Golden_Breath ？