不知道为什么,核心做法没变,换了一种写法怎么就过了?
```cpp
#include <iostream>
#include <vector>
using namespace std;
const int N = 110, M = 1 << 10;
int n, m;
int g[N], cnt[M];
int f[2][M][M];
vector<int> state;
vector<int> head[M];
bool check(int st) { return !(st & st >> 1 || st & st >> 2); }
int count(int st) {
int res = 0;
while (st) res += st & 1, st >>= 1;
return res;
}
int main() {
cin >> n >> m;
for(int i = 1; i <= n; i ++)
for(int j = 0; j < m; j ++) {
char ch;
cin >> ch;
if(ch == 'H') g[i] += 1 << j;
}
for (int st = 0; st < 1 << m; ++ st)
if (check(st))
state.push_back(st), cnt[st] = count(st);
for (int cur_st: state)
for (int pre_st: state)
if (!(cur_st & pre_st))
head[cur_st].push_back(pre_st);
for (int i = 1; i <= n; ++ i)
for (int s1: state)
if (!(g[i] & s1))
for (int s2: head[s1])
for (int s3: head[s2])
if (!(s1 & s3))
f[i&1][s1][s2] = max(f[i&1][s1][s2], f[i-1&1][s2][s3] + cnt[s1]);
int res = 0;
for (int st: state)
for (int pre: head[st])
res = max(res, f[n&1][st][pre]);
cout << res << endl;
return 0;
}
```
玄学
by ZYK_luogu @ 2023-10-05 13:01:29
@[ZYK_luogu](/user/742157) 求解答
by ZYK_luogu @ 2023-10-05 13:02:24