洛谷 P1622 释放囚犯【区间dp】

原题链接：https://www.luogu.com.cn/problem/P1622

题目描述

Caima 王国中有一个奇怪的监狱，这个监狱一共有 P 个牢房，这些牢房一字排开，第 i 个紧挨着第 i+1 个（最后一个除外）。现在正好牢房是满的。

上级下发了一个释放名单，要求每天释放名单上的一个人。这可把看守们吓得不轻，因为看守们知道，现在牢房中的 P 个人，可以相互之间传话。如果某个人离开了，那么原来和这个人能说上话的人，都会很气愤，导致他们那天会一直大吼大叫，搞得看守很头疼。如果给这些要发火的人吃上肉，他们就会安静点。

输入格式

第一行两个整数 P 和 Q，Q 表示释放名单上的人数；

第二行 Q 个整数，表示要释放哪些人，保证按递增的顺序给出。

输出格式

仅一行，表示最少要给多少人次送肉吃。

输入输出样例

输入 #1

20 3
3 6 14

输出 #1

35

说明/提示

样例说明 #1

先释放 14 号监狱中的罪犯，要给 1 到 13 号监狱和 15 到 20 号监狱中的 19 人送肉吃；再释放 6 号监狱中的罪犯，要给 1 到 5 号监狱和 7 到 13 号监狱中的 12 人送肉吃；最后释放 3 号监狱中的罪犯，要给 1 到 2 号监狱和 4 到 5 号监狱中的 4 人送肉吃。

数据规模与约定

• 对于 50%50% 的数据，1≤P≤100，1≤Q≤5；
• 对于 100%100% 的数据，1≤P≤1e3，1≤Q≤100，Q≤P，保证释放的人所在的牢房编号按递增的顺序给出。

解题思路：

首先题目说了释放的人的所在牢房编号按递增的顺序给出，所以不需要在排序了，现在唯一影响吃肉数量的因素就是释放的顺序，先释放谁后释放谁的问题，对于一个区间[l,r]，我们考虑最后一个释放的位置为k，那么释放k之后，就会形成俩个新的需要处理的区间f[l,k-1]，f[k+1,r]，这个不就是经典的区间dp了吗，然后我们考虑区间dp进行处理即可。

区间dp处理过程：

状态定义：

定义f[l][r]表示释放a数组的a[l],a[l+1],a[l+2],...,a[r]所需要的最少吃肉数量。

初始化：

我们需要设置俩个哨兵，方便后面的状态转移，设置哨兵a[0]=0,a[m+1]=n+1;这俩个哨兵分别表示第0个位置和第n+1个位置各自都有一个囚犯，这俩个囚犯是虚拟的，并不需要进行实际处理，只是为了方便后面状态转移,哨兵是为了在处理区间[1,m]的左右俩侧时方便计算才设置的。

状态转移： 

枚举优先处理区间中的k点，也就是枚举分界点，优先处理分解点，然后处理俩侧俩个区间

最后一步是处理k,a[r+1]-a[l-1]-1表示的是区间[l,r]数的个数，我们释放k,所以需要吃肉的数量为a[r+1]-a[l-1]-1-1

• f[l][r] = min(f[l][r], f[l][k - 1] + f[k + 1][r] + a[r + 1] - a[l - 1] - 1 - 1);

最终答案：

答案就是处理a[1],a[2],...,a[m]这个区间所需要吃肉的最少数量f[1][m]

时间复杂度：区间dp第一维枚举区间长度，时间为O(Q)，第二维枚举区间左端点，时间为O(Q)，第三维枚举区间分界点，时间为O(Q)，最终时间复杂度为O(Q^3)，Q=100，所以时间大概为1e6，这个时间是肯定可以过的。

空间复杂度：区间dp数组f是二维的，空间复杂度为O(Q^2)，Q=100，所以花费空间非常小，这个题目给了125M,空间肯定足够。

cpp代码如下：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;
typedef long long LL;
typedef pair<int, int> PII;

const int N = 110;
int n, m;
int a[N];
int f[N][N];

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
        scanf("%d", &a[i]);

    a[0] = 0, a[m + 1] = n + 1;  //设置哨兵
    for (int len = 1; len <= m; len++)  //枚举区间长度
        for (int l = 1; l + len - 1 <= m; l++)  //枚举区间左端点
        {
            int r = l + len - 1;
            f[l][r] = 1e9;
            //枚举优先处理区间中的k点，也就是枚举分界点，优先处理分解点，然后处理俩侧俩个区间
            for (int k = l; k <= r; k++)
                f[l][r] = min(f[l][r], f[l][k - 1] + f[k + 1][r] + a[r + 1] - a[l - 1] - 1 - 1);
        }
    //答案就是处理a[1],a[2],...,a[m]这个区间所需要吃肉的最少数量
    cout << f[1][m] << endl;
    return 0;
}