Air Cownditioning II

题意

有 N 头牛，每头牛占据一个牛棚区间 [s_i, t_i]，并要求这些位置至少降温 c_i。

有 M 台空调。第 i 台空调覆盖区间 [a_i, b_i]，能让这些位置降温 p_i，开启花费为 m_i。

选择若干台空调，使所有牛所在位置都满足降温要求，求最小花费。

思路

先看一个 01 选择序列风格的暴力：

cpp

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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-11 17:05
 * update_at: 2026-07-11 17:06
 */
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 25;
const int MAXM = 15;
const int MAXS = 100;
const int INF = 1e9;

int n, m;
int need[MAXS + 5];

int a[MAXM], b[MAXM], p[MAXM], cost[MAXM];
int choose_ac[MAXM]; // choose_ac[i] 表示第 i 台空调是否开启
int ans = INF;

void check_current_choice() {
    int cool[MAXS + 5];
    memset(cool, 0, sizeof(cool));

    int total_cost = 0;
    for (int i = 1; i <= m; i++) {
        if (choose_ac[i] == 0) {
            continue;
        }
        total_cost += cost[i];
        for (int x = a[i]; x <= b[i]; x++) {
            cool[x] += p[i];
        }
    }

    for (int x = 1; x <= MAXS; x++) {
        if (cool[x] < need[x]) {
            return;
        }
    }

    if (total_cost < ans) {
        ans = total_cost;
    }
}

// 第 dep 层决定第 dep 台空调开不开。
void dfs_choose(int dep) {
    if (dep == m + 1) {
        check_current_choice();
        return;
    }

    choose_ac[dep] = 0;
    dfs_choose(dep + 1);

    choose_ac[dep] = 1;
    dfs_choose(dep + 1);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;

    for (int i = 1; i <= n; i++) {
        int s, t, c;
        cin >> s >> t >> c;
        for (int x = s; x <= t; x++) {
            need[x] = c;
        }
    }

    for (int i = 1; i <= m; i++) {
        cin >> a[i] >> b[i] >> p[i] >> cost[i];
    }

    dfs_choose(1);

    cout << ans << '\n';

    return 0;
}

这个暴力把每台空调看成一层选择：choose_ac[i] = 0/1 表示第 i 台空调不开或开。递归生成完整选择序列后，再统一检查所有牛棚位置是否达标，并更新最小花费。

为什么可以这样做？因为本题 $M \leqslant 10$ ，空调集合最多只有：

2^{10} = 1024

种。

满分代码可以用 bitmask 写得更短。令 mask 的第 i 位表示第 i 台空调是否开启：

如果这一位是 1，就把这台空调的花费加入总花费；
同时把它覆盖区间 [a_i, b_i] 中每个位置的降温量加上 p_i。

为了检查方便，先把每个牛棚位置的需求存到 need[x] 中。没有牛的位置需求为 0。

对每个 mask，模拟得到 cool[x] 后，只要所有位置都满足：

text

1cool[x] >= need[x]

这个集合就是可行的，用它的花费更新答案即可。

代码

cpp

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
70
71
72
73/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-11 17:05
 * update_at: 2026-07-11 17:06
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 25;
const int MAXM = 15;
const int MAXS = 100;
const int INF = 1e9;

int n, m;
int need[MAXS + 5]; // need[x] 表示第 x 个牛棚需要降温多少

int a[MAXM], b[MAXM], p[MAXM], cost[MAXM];

bool check(int mask, int &total_cost) {
    int cool[MAXS + 5];
    memset(cool, 0, sizeof(cool));
    total_cost = 0;

    for (int i = 0; i < m; i++) {
        if ((mask & (1 << i)) == 0) {
            continue;
        }
        total_cost += cost[i];
        for (int x = a[i]; x <= b[i]; x++) {
            cool[x] += p[i];
        }
    }

    for (int x = 1; x <= MAXS; x++) {
        if (cool[x] < need[x]) {
            return false;
        }
    }
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;

    for (int i = 1; i <= n; i++) {
        int s, t, c;
        cin >> s >> t >> c;
        for (int x = s; x <= t; x++) {
            need[x] = c;
        }
    }

    for (int i = 0; i < m; i++) {
        cin >> a[i] >> b[i] >> p[i] >> cost[i];
    }

    int ans = INF;
    for (int mask = 0; mask < (1 << m); mask++) {
        int total_cost = 0;
        if (check(mask, total_cost) && total_cost < ans) {
            ans = total_cost;
        }
    }

    cout << ans << '\n';

    return 0;
}

复杂度

一共有 $2^M$ 个空调子集。每个子集最多处理 M 台空调，每台空调最多影响 100 个牛棚位置。

时间复杂度为 $O(2^M \cdot M \cdot 100)$ 。

空间复杂度为 $O(100 + M)$ 。

总结

本题是很标准的子集枚举。

看到 $M \leqslant 10$ ，就应该优先想到枚举所有空调开关状态。递归 01 选择序列和 bitmask 本质相同，都是在遍历所有空调集合。

目录

题意

思路

代码

复杂度

总结