P2704 [NOI2001] 炮兵阵地
依然是状态压缩，一层的状态不仅取决于上一层了，还与上上层有关，所以DP时要三维空间，第一维枚举每一层可以滚动。
查看代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
| #include <iostream>
#include <cstdio>
using namespace std;
const int N = 2e3 + 10;
bool avai[110][12];
int n, m, cnt[110], state[110][N], num[110][N], f[2][N][N];
int main ()
{
cin >> n >> m;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
{
char c;
cin >> c;
avai[i][j] = c == 'P';
}
for (int k = 0; k < n; k++)
for (int i = 0; i < 1 << m; i++)
{
bool flag = true;
for (int j = 0; j < m; j++)
if (((i >> j & 1) & (i >> j + 1 & 1))
|| ((i >> j & 1) & (i >> j + 2 & 1))
|| (!avai[k][j] && i >> j & 1))
{
flag = false;
break;
}
if (!flag)
continue;
state[k][++cnt[k]] = i;
for (int j = i; j; j >>= 1)
num[k][cnt[k]] += j & 1;
}
for (int i = 1; i <= cnt[1]; i++)
for (int j = 1; j <= cnt[0]; j++)
if ((state[1][i] & state[0][j]) == 0)
f[1][i][j] = num[0][j] + num[1][i];
for (int i = 2; i < n; i++)
for (int x = 1; x <= cnt[i]; x++)
for (int y = 1; y <= cnt[i - 1]; y++)
if ((state[i][x] & state[i - 1][y]) == 0)
for (int z = 1; z <= cnt[i - 2]; z++)
if ((state[i][x] & state[i - 2][z]) == 0 && (state[i - 1][y] & state[i - 2][z]) == 0)
f[i & 1][x][y] = max(f[i & 1][x][y], f[i - 1 & 1][y][z] + num[i][x]);
int res = 0;
for (int i = 1; i <= cnt[n - 1]; i++)
for (int j = 1; j <= cnt[n - 2]; j++)
res = max(res, f[n - 1 & 1][i][j]);
cout << res;
return 0;
}
|