原题链接：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
先释放?14?号监狱中的罪犯，要给?1?到 13?号监狱和 15?到 20?号监狱中的 19?人送肉吃；再释放?6?号监狱中的罪犯，要给?1?到?5?号监狱和?7?到 13?号监狱中的 12?人送肉吃；最后释放?3?号监狱中的罪犯，要给?1?到?2?号监狱和 4?到?5?号监狱中的?4?人送肉吃。
首先题目说了释放的人的所在牢房编号按递增的顺序给出，所以不需要在排序了，现在唯一影响吃肉数量的因素就是释放的顺序，先释放谁后释放谁的问题，对于一个区间[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;
}