本文主要是介绍洛谷 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;
}这篇关于洛谷 P1622 释放囚犯【区间dp】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
