最近在补全提高课所有题目的题解，宣传一下汇总的地方提高课题解补全计划

题目描述

有 $n$ 座 山 和 $m$ 只 abc 喵酱，$P$ 位 饲养员 （编号都从 $1$ 到 $n$）

第 $i$ 座 山 和第 $i-1$ 座 山 相隔 $D_i$ 的距离

第 $i$ 只 喵酱 会在第 $H_i$ 座 山 上玩耍，直到 $T_i$ 时刻 停止，并等待 饲养员 来接他

所有的 饲养员 初始 都在第 $1$ 座山上，现安排这些 饲养员 的 出发时刻（可以是 负数）

饲养员 以 单位时间内行走1个单位长度 的速度沿 坐标轴 出发，接走经过的 山 上所有 等待中 的 喵酱

喵酱 很心急，求一种 饲养员 的 出发方案，使得所有 喵酱 的 等待时间之和最少

分析

前置芝士：AcWing 301. 任务安排2【斜率优化DP模板】

首先用 前缀和 $sd_i$ 表示第 $i$ 座 山 到 起点 第 $1$ 座 山 的 距离

对于每只 喵酱 一经等待就恰好被接走 的 饲养员 出发时间 为：$t_i - sd_{h_i}$ （饲养员到达时刚好接走）

令 $a_i = t_i - sd_{h_i}$ 表示第 $i$ 只 喵酱 的 最早接走的出发时刻

那么对于第 $k$ 时刻 出发 的 饲养员，他能接走的 喵酱 满足：$a_i \le k$

因此为了方便接下来 动态规划 的阶段划分，我们不妨按 $a_i$ 对 喵酱 们进行 排序

闫氏DP分析法

状态表示—集合 $f_{i,j}$：已经派出 $i$ 名 饲养员，且接走了前 $j$ 只 喵酱 的方案

状态表示—属性 $f_{i,j}$：方案中，每个 喵酱 的 等待时间之和 最小 $Min$

状态计算：

考虑 $i-1$ 阶段接走 $k(0 \le k \lt j)$ 只 喵酱，为了让 $k+1 \sim j$ 的 喵酱 等待时间之和最少

可以列出如下式子：设第 $i$ 名 饲养员 的 出发时间 为 $T$

$$ cost = \sum_{u = k + 1}^j (a_u - T) $$

根据 贪心的思想，应让第 $i$ 名 饲养员 的 出发时间 为 $a_{j}$ （读者自证不难）

对于第 $i$ 名 饲养员（机器） 带走连续一段的 $k+1 \sim j$ 只 喵酱（任务），就是 任务安排 裸题了

于是有如下 转移方程：

$$ \begin{aligned} f_{i,j} &= \min \bigg\{{ f_{i-1, k} + \sum_{u = k + 1}^j (a_j - a_u) }\bigg\} \quad (0 \le k \lt j) \\\\ f_{i,j} &= \min \bigg\{{ f_{i-1, k} + \sum_{u = k + 1}^j a_j - \sum_{u = k + 1}^j a_u }\bigg\} \quad (0 \le k \lt j) \\\\ 预处理前缀和： f_{i,j} &= \min \bigg\{{ f_{i-1, k} + a_j \times (j - k) - (s_j - s_k) }\bigg\} \\\\ 提出常量： f_{i,j} &= j \times a_j - s_j + \min \bigg\{{ f_{i-1, k} + s_k - a_j \times k }\bigg\} \\\\ \end{aligned} $$

出现 $j \times k$ 的项，考虑 斜率优化：令 $\begin{cases} x_k = k \\\\ k_j = a_j \\\\ y_k = f_{i-1,k} + s_k \end{cases}$，则原式化为：

$$ f_{i,j} = j \times a_j - s_j + \min \bigg\{{ y - kx }\bigg\} $$

接下来就是 模板 里经典的：维护 下凸壳的点集，求 第一个 出现在 直线 上的 点

由于本题中的直线斜率 $a_j$ 我们事先进行了 排序，故他是 单调递增 的

我们就可以同 任务安排2 中一样用 单调队列 在 队头 维护 大于 $k$ 的 最小斜率

直接套 斜率优化DP 的模板即可，不需要任何 二分/平衡树/CDQ优化

Code

时间复杂度： $O(PM)$

空间复杂度： $O(PM)$

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

using namespace std;

typedef long long LL;

const int N = 1e5 + 10, M = 110;

int n, m, p, que[N];
LL sd[N], a[N], s[N], f[M][N];

LL y(int k, int i) {
    return f[i - 1][k] + s[k];
}
int main()
{
    scanf("%d%d%d", &n, &m, &p);
    for (int i = 2; i <= n; i ++ ) scanf("%lld", &sd[i]), sd[i] += sd[i - 1];
    for (int i = 1, h, t; i <= m; i ++ ) scanf("%d%d", &h, &t), a[i] = t - sd[h];

    sort(a + 1, a + m + 1);
    for (int i = 1; i <= m; i ++ ) s[i] = s[i - 1] + a[i];

    memset(f, 0x3f, sizeof f);
    for (int i = 0; i <= p; ++i) f[i][0] = 0;

    for (int i = 1; i <= p; i ++ )
    {
        int hh = 0, tt = 0;
        for (int j = 1; j <= m; j ++ )
        {
            while (hh < tt && y(que[hh + 1], i) - y(que[hh], i) <=
                              a[j] * (que[hh + 1] - que[hh])) hh ++ ;
            f[i][j] = j * a[j] - s[j] + y(que[hh], i) - a[j] * que[hh];
            while (hh < tt && (y(que[tt], i) - y(que[tt - 1], i)) * (j - que[tt]) >=
                              (y(j, i) - y(que[tt], i)) * (que[tt] - que[tt - 1])) tt -- ;
            que[ ++ tt] = j;
        }
    }
    printf("%lld\n", f[p][m]);
    return 0;
}

还可以用滚动数组优化

空间复杂度： $O(M)$

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

using namespace std;

typedef long long LL;

const int N = 1e5 + 10, M = 110;

int n, m, p, que[N];
LL sd[N], a[N], s[N], f[2][N];

LL y(int k, int i) {
    return f[i - 1 & 1][k] + s[k];
}
int main()
{
    scanf("%d%d%d", &n, &m, &p);
    for (int i = 2; i <= n; i ++ ) scanf("%lld", &sd[i]), sd[i] += sd[i - 1];
    for (int i = 1, h, t; i <= m; i ++ ) scanf("%d%d", &h, &t), a[i] = t - sd[h];

    sort(a + 1, a + m + 1);
    for (int i = 1; i <= m; i ++ ) s[i] = s[i - 1] + a[i];

    memset(f, 0x3f, sizeof f);
    for (int i = 0; i <= 1; ++i) f[i][0] = 0;

    for (int i = 1; i <= p; i ++ )
    {
        int hh = 0, tt = 0;
        for (int j = 1; j <= m; j ++ )
        {
            while (hh < tt && y(que[hh + 1], i) - y(que[hh], i) <=
                              a[j] * (que[hh + 1] - que[hh])) hh ++ ;
            f[i & 1][j] = j * a[j] - s[j] + y(que[hh], i) - a[j] * que[hh];
            while (hh < tt && (y(que[tt], i) - y(que[tt - 1], i)) * (j - que[tt]) >=
                              (y(j, i) - y(que[tt], i)) * (que[tt] - que[tt - 1])) tt -- ;
            que[ ++ tt] = j;
        }
    }
    printf("%lld\n", f[p & 1][m]);
    return 0;
}