释放囚犯

题意

有 P 个连续牢房，释放名单中有 Q 个囚犯需要依次被放出来。

每次释放一个人时，当前这整段连续监区里，除了他自己以外，其余还关着的人都要送肉安抚。要求安排释放顺序，使总代价最小。

思路

最直接的办法是暴力枚举今天先释放名单里的哪一个人。

先看一个可以直接验证想法的朴素解：

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#include <bits/stdc++.h>
using namespace std;

static int P, Q;
static vector<int> need_release;
static vector<int> released;

int dfs(vector<int> cur) {
    if (cur.empty()) {
        return 0;
    }

    int best = INT_MAX;
    for (int x : cur) {
        int left = 0;
        int right = P + 1;
        for (int y : released) {
            if (y < x) {
                left = max(left, y);
            } else if (y > x) {
                right = min(right, y);
            }
        }
        int cost = right - left - 2;

        vector<int> next = cur;
        next.erase(find(next.begin(), next.end(), x));
        released.push_back(x);
        best = min(best, cost + dfs(next));
        released.pop_back();
    }
    return best;
}

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

    cin >> P >> Q;
    need_release.resize(Q);
    for (int i = 0; i < Q; ++i) {
        cin >> need_release[i];
    }

    released.clear();
    released.push_back(0);
    released.push_back(P + 1);
    cout << dfs(need_release) << '\n';
    return 0;
}

brute.cpp 会直接搜索释放顺序，适合小数据对拍，但正式数据下会反复遇到同样的子区间。

关键观察是：如果当前只关心两个已释放边界 a[l] 和 a[r] 之间的那批目标囚犯，那么“第一个释放谁”一旦确定，左右两边就完全独立了。

于是先把释放名单两端补上哨兵：

左边 0
右边 P+1

定义 dp[l][r] 表示释放 (a[l], a[r]) 之间所有目标囚犯的最小总代价。

如果先释放的是中间某个 a[k]，那么：

左边代价是 dp[l][k]
右边代价是 dp[k][r]
当前固定代价是 a[r] - a[l] - 2

这张表展示几个典型状态的含义：

状态	表示什么
`dp[2][3]`	边界 `a[2], a[3]` 之间没有待释放囚犯，代价是 `0`
`dp[1][4]`	只考虑 `a[1]` 和 `a[4]` 之间那段监区的最优代价
`dp[0][Q+1]`	整个问题的最终答案

读这张表时，重点是理解 dp[l][r] 不是原牢房编号区间，而是“释放名单位置上的区间”。这样一来，状态数只和 Q 有关，而不是和 P 有关。

因此转移就是：

dp[l][r] = min(dp[l][k] + dp[k][r] + a[r] - a[l] - 2)

DP 公式

把释放位置排序，并加入边界 $a_0=0$ 、 $a_{q+1}=P+1$ 。设 $dp_{l,r}$ 表示释放 $(a_l,a_r)$ 之间所有目标囚犯的最小总代价。若选择第 $k$ 个囚犯最后释放，则：

dp_{l,r}=\min_{l<k<r}\left(dp_{l,k}+dp_{k,r}+a_r-a_l-2\right)

当 $r=l+1$ 时区间内没有待释放囚犯：

dp_{l,l+1}=0

最终答案为：

dp_{0,q+1}

枚举所有 k，取最小值即可。

公式解释：在边界 a_l 和 a_r 之间，若最后释放第 k 个目标囚犯，则左右两边已经分别最优释放完。最后释放时需要给这个监区里剩余的人补偿，代价就是 a_r-a_l-2。

代码

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#include <bits/stdc++.h>
using namespace std;

const int INF = 0x3f3f3f3f;

static int a[105];
static int dp[105][105];

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

    int P, Q;
    cin >> P >> Q;
    a[0] = 0;
    for (int i = 1; i <= Q; ++i) {
        cin >> a[i];
    }
    a[Q + 1] = P + 1;

    for (int len = 2; len <= Q + 1; ++len) {
        for (int l = 0; l + len <= Q + 1; ++l) {
            int r = l + len;
            dp[l][r] = INF;
            for (int k = l + 1; k < r; ++k) {
                dp[l][r] = min(dp[l][r], dp[l][k] + dp[k][r] + a[r] - a[l] - 2);
            }
            if (dp[l][r] == INF) {
                dp[l][r] = 0;
            }
        }
    }

    cout << dp[0][Q + 1] << '\n';
    return 0;
}

复杂度

区间 DP 需要枚举区间长度、左端点和第一个释放点，所以时间复杂度是 $O(Q^3)$ ，空间复杂度是 $O(Q^2)$ 。

总结

这题的关键是把原问题缩到释放名单上来做。补上哨兵之后，“先释放谁”就自然变成了一个标准区间 DP。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

目录

题意

思路

DP 公式

代码

复杂度

总结

一图流解析