ZYK_luogu @ 2023-10-04 13:17:11
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
typedef long long LL;
const int N = 103, M = 10, S = 1 << M;
int n, m, g[N], cnt[S];
vector<int> states;
vector<int> head[S];
LL f[2][S][S];
int main() {
cin >> n >> m;
for(int i = 1; i <= n; i ++)
for(int j = 0; j < m; j ++) {
char c; cin >> c;
if(c == 'H') g[i] += 1 << j;
}
for(int s = 0; s < (1 << m); s ++)
if(!(s & s >> 1 || s & s >> 2)) {
states.push_back(s);
int s_ = s, tot = 0;
while(s_) tot += s_ & 1, s_ >>= 1;
cnt[s] = tot;
}
for(int i = 0; i < (int)states.size(); i ++)
for(int j = 0; j < (int)states.size(); j ++) {
int s1 = states[i], s2 = states[j];
if(!(s1 & s2)) head[s1].push_back(s2);
}
for(int i = 1; i <= n + 2; i ++)
for(int a = 0; a < (int)states.size(); a ++) {
int s1 = states[a];
if(!(g[i] & s1)) {
for(int b = 0; b < (int)head[s1].size(); b ++) {
int s2 = states[b];
for(int c = 0; c < (int)head[s2].size(); c ++) {
int s3 = states[c];
if(!(s1 & s3))
f[i & 1][s1][s2] = max(f[i & 1][s1][s2], f[(i - 1) & 1][s2][s3] + cnt[s1]);
}
}
}
}
cout << f[(n + 2) & 1][0][0];
return 0;
}by ZYK_luogu @ 2023-10-05 13:01:29
不知道为什么，核心做法没变，换了一种写法怎么就过了？
#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:02:24
@ZYK_luogu 求解答