[数据结构与算法]洛谷P1622 释放囚犯【区间DP】【绿】

Date：2022.03.22
题目描述
Caima 王国中有一个奇怪的监狱，这个监狱一共有 P 个牢房，这些牢房一字排开，第 i 个紧挨着第 i+1 个（最后一个除外）。现在正好牢房是满的。
上级下发了一个释放名单，要求每天释放名单上的一个人。这可把看守们吓得不轻，因为看守们知道，现在牢房中的 P 个人，可以相互之间传话。如果某个人离开了，那么原来和这个人能说上话的人，都会很气愤，导致他们那天会一直大吼大叫，搞得看守很头疼。如果给这些要发火的人吃上肉，他们就会安静点。
输入格式
第一行两个整数 PP 和 QQ，QQ 表示释放名单上的人数；
第二行 QQ 个整数，表示要释放哪些人。
输出格式
仅一行，表示最少要给多少人次送肉吃。
输入输出样例
输入 #1复制
20 3
3 6 14
输出 #1复制
35
说明/提示
样例说明 #1
先释放 14 号监狱中的罪犯，要给 1 到 13 号监狱和 15 到 2020 号监狱中的 19 人送肉吃；再释放 6 号监狱中的罪犯，要给 1 到 5 号监狱和 7 到 13 号监狱中的 12 人送肉吃；最后释放 3 号监狱中的罪犯，要给 1 到 2 号监狱和 4 到 5 号监狱中的 4 人送肉吃。
数据规模与约定
对于 50% 的数据，1≤P≤100，1≤Q≤5；
对于 100% 的数据，1≤P≤10^3，1≤Q≤100，Q≤P。

思路：试过了二进制枚举状压（一看就太大了）、硬枚举等方法…都会t。我们倒着想，先释放最后一个囚犯，等价于将与其左右相邻的两个区间合并为一个区间的花费（参考石子合并），合并完了就将这个囚犯所在的位置（也就是两个被合并区间的间断点）补上，这样才合并为一个完整的区间；类比这样一直合并…直到释放第一个囚犯，相当于把与其紧邻的两个大区间合并为一个区间，至此完成合并，所以这个过程完全等价于石子合并。
我们预处理出给定的q+1个区间，按石子合并的思想来区间dp，但要注意每次合并编号为$[l,r]$的区间，其中会有$len?1=r?l+1?1$个间断点划分出$len$个区间，但由于有一个间断点是我们枚举的$k$【也就是合并$[l,r]$这个大区间是由哪两个$f[l][k]、f[k+1][r]$得来的（我们也可将这一步看做要填入的囚犯是在编号为$[k,k+1]$这个区间之内的点，填入即连接了$f[l][k]和f[k+1][r]$为完整的$f[l][r]$）】，并且到这一步时，$f[l][k]和f[k+1][r]$已分别合并为两个区间了，因此这一步除了区间合并的贡献，我们还有当前点对$[l,k]和[k+1,r]$里的其它已经填补的间断点的贡献（这里自己想想吧，说的有点乱），显然这些间断点共有$len?1?1$个，因为有一个是当前编号为$[k,k+1]$之间的点，因此每一步区间合并，都要加上len-1-1。
可能有点乱，我们清晰定义一下$f[l][r]:$将所有编号为$[l,r]$的区间合并所需的最小花费（考虑间断点的贡献）。
代码如下：

#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int n,m,f[N][N],a[N],b[N],sum[N];
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++) cin>>a[i];b[1]=a[1]-1;sum[1]=b[1];
    for(int i=2;i<=m;i++)
    {
        b[i]=a[i]-a[i-1]-1;
        sum[i]=sum[i-1]+b[i];
    }
    b[m+1]=n-a[m];sum[m+1]=sum[m]+b[m+1];
    for(int len=2;len<=m+1;len++)
        for(int l=1;l+len-1<=m+1;l++)
        {
            int r=l+len-1;f[l][r]=1e9;
            for(int k=l;k<r;k++)
                f[l][r]=min(f[l][r],f[l][k]+f[k+1][r]+sum[r]-sum[l-1]+len-1-1);
        }
    cout<<f[1][m+1];
    return 0;
}