AcWing 292. 炮兵阵地
原题链接
中等
作者:
MILLOPE
,
2019-06-12 10:00:48
,
所有人可见
,
阅读 1106
题解
题解传送门
code
#include <bits/stdc++.h>
using namespace std;
const int maxn = 120;
template <typename T>
inline void read(T &s) {
s = 0;
T w = 1, ch = getchar();
while (!isdigit(ch)) { if (ch == '-') w = -1; ch = getchar(); }
while (isdigit(ch)) { s = (s << 1) + (s << 3) + (ch ^ 48); ch = getchar(); }
s *= w;
}
int n, m, cnt, ans;
int a[maxn], s[maxn], num[maxn];
int f[maxn][maxn][maxn];
int main() {
read(n), read(m);
for (int i = 1; i <= n; ++i) {
for (int j = 0; j < m; ++j) {
char ch; cin >> ch;
if (ch == 'H') a[i] |= (1 << j);
}
}
for (int i = 0; i < (1 << m); ++i) {
if ((i & (i << 1)) || (i & (i << 2))) continue;
s[++cnt] = i;
int t = i;
while (t)
num[cnt] += t & 1, t >>= 1;
}
for (int i = 1; i <= cnt; ++i) {
if (s[i] & a[1]) continue;
f[1][1][i] = num[i];
}
for (int i = 2; i <= n; ++i) {
for (int j = 1; j <= cnt; ++j) {
if (s[j] & a[i]) continue;
for (int k = 1; k <= cnt; ++k) {
if (s[j] & s[k]) continue;
for (int l = 1; l <= cnt; ++l) {
if (s[j] & s[l]) continue;
if (s[k] & s[l]) continue;
f[i][k][j] = max(f[i][k][j], f[i - 1][l][k] + num[j]);
}
}
}
}
ans = 0;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= cnt; ++j) {
for (int k = 1; k <= cnt; ++k) {
ans = max(ans, f[i][j][k]);
}
}
}
printf("%d\n", ans);
return 0;
}