RenaMoe's Blog

念念不忘，必有回响

0%

题解 P2704 [NOI2001]炮兵阵地

发表于 更新于 分类于 ， Valine：

题目

珍爱头发，远离状压

首先如果没做过状压的话，出门右转

思路

这道题。。。数据范围很状压

显然，把每一行的地图（有山为1，否则为0）压到一个数里

把枚举的状态压成有炮为1，否则为0

把有解的情况存下来，便于枚举，并预处理每种情况的炮兵个数

现在用\(f_{i,j,k}\)表示第\(i\)行是状态\(j\)，是由状态\(k\)转移来的，最大的炮兵个数

单独处理第一行和第二行

后面\(dp\)的时候注意:

如何使一列中的每三行只有一个炮兵？

保证\(k1\) & \(k2\), \(k2\) & \(k3\), \(k1\) & \(k3\)都为0即可（显然）

另外，空间有点。。。建议滚动数组

代码

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <cstdio>
#include <cctype>
#include <algorithm>
#include <vector>

using namespace std;

template<typename T> inline void read(T &x) {
    x = 0; T k = 1; char in = getchar();
    while (!isdigit(in)) { if (in == '-') k = -1; in = getchar(); }
    while (isdigit(in)) x = x * 10 + in - '0', in = getchar();
    x *= k;
}

const int M = 1<<11;
const int N = 105;

int n, m, maxn, ans;
int mp[N], f[3][M][M];
vector<int> d, v;// 可行状态的对应的炮兵个数
char in[15];

// 计算每种情况的炮兵个数
inline int count(int x) {
    int re = 0;
    for (int i = 0; i <= 30; ++i)
        if (x & (1 << i))
            re++;
    return re;
}

int main() {
    read(n), read(m);
    maxn = (1 << m) - 1;
    for (int i = 0; i < n; ++i) {
        scanf("%s", in);
        //处理地图
        for (int j = 0; j < m; ++j)
            if (in[j] == 'H')
                mp[i] |= 1 << j;
    }
    // 预处理可行状态
    for (int i = 0; i <= maxn; ++i)
        if ((i & (i >> 1)) == 0 && (i & (i >> 2)) == 0)
            d.push_back(i), v.push_back(count(i));
    // 单独处理一二行
    for (int i = 0; i < d.size(); ++i)
        if ((d[i] & mp[0]) == 0)// 一贯的保证可行
            f[0][d[i]][0] = v[i];
    for (int i = 0; i < d.size(); ++i)
        if ((d[i] & mp[1]) == 0)
            for (int j = 0; j < d.size(); ++j)
                if ((d[j] & d[i]) == 0)
                    f[1][d[i]][d[j]] = max(f[1][d[i]][d[j]], f[0][d[j]][0] + v[i]);
    // 愉快的dp
    for (int i = 2; i < n; ++i)// 行数
        for (int j = 0; j < d.size(); ++j)// 该行
            if ((d[j] & mp[i]) == 0)
                for (int k = 0; k < d.size(); ++k)// 上一行
                    if ((d[k] & d[j]) == 0)
                        for (int l = 0; l < d.size(); ++l)// 上二行
                            if ((d[l] & d[k]) == 0 && (d[l] & d[j]) == 0)
                                f[i%3][d[j]][d[k]] = max(f[i%3][d[j]][d[k]], f[(i-1)%3][d[k]][d[l]] + v[j]);// 重点
    // 统计最后一行的最大值
    for (int i = 0; i < d.size(); ++i)
        for (int j = 0; j < d.size(); ++j)
            ans = max(ans, f[(n-1)%3][d[i]][d[j]]);
    printf("%d\n", ans);
}