AcWing 292. 炮兵阵地 滚动数组优化
原题链接
中等
作者:
Snrise
,
2024-04-06 16:09:44
,
所有人可见
,
阅读 2
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#define endl '\n'
#define int long long
using namespace std;
const int M = 12;
const int K = 1 << M;
const int N = 110;
int g[N];
int f[2][K][K];
int st[K], cnt;
int num[K];
int n, m;
signed main(void)
{
std::ios::sync_with_stdio(false);
cin >> n >> m;
// for (int i = 1; i <= n; i++)
// {
// for (int j = 0; j < m; j++)
// {
// char c;
// cin >> c;
// if (c == 'P')
// {
// g[i] += 1 << (m - j - 1);
// }
// }
// }
for (int i = 1; i <= n; i++)
{
char s[15];
cin >> s;
for (int j = 0; j < m; j++)
{
int x = (s[j] == 'P');
g[i] = (g[i] << 1) + x;
}
}
for (int i = 0; i < (1 << m); i++)
{
if (!(i & (i >> 1)) && !(i & (i >> 2)))
{
st[cnt++] = i;
for (int j = 0; j < m; j++)
{
num[i] += (i >> j & 1);
}
}
}
for (int i = 1; i <= n + 2; i++)
{
for (int a = 0; a < cnt; a++)
{
for (int b = 0; b < cnt; b++)
{
f[i & 1][a][b] = 0;
for (int c = 0; c < cnt; c++)
{
if (!(st[a] & st[b]) && !(st[a] & st[c]) && !(st[b] & st[c]) && (st[a] & g[i]) == st[a] && (st[b] & g[i - 1]) == st[b])
{
f[i & 1][a][b] = max(f[i & 1][a][b], f[(i - 1) & 1][b][c] + num[st[a]]);
}
}
}
}
}
cout << f[(n + 2) & 1][0][0] << endl;
return 0;
}