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

题目描述

有 $n$ 个 任务 排成一个 序列，顺序不得改变，其中第 $i$ 个 任务 的 耗时 为 $t_i$， 费用系数 为 $c_i$

现需要把该 $n$ 个 任务 分成 若干批 进行加工处理

每批次的 段头，需要 额外消耗 $S$ 的时间启动机器。每一个任务的 完成时间 是所在 批次 的 结束时间。

完成一个任务的 费用 为：从 $0$ 时刻 到该任务 所在批次结束 的时间 $t$ 乘以 该任务 费用系数 $c$

分析

为方便读者更好的阅读本题解，建议先看一下我写的上一篇，因为本篇中不会对重复地方进行讲解
AcWing 301. 任务安排2【斜率优化DP模板】

本题 相较于 上一题 的不同之处在于：$-512 \le t_i \le 512$

该限制使得 $t_i$ 的 前缀和 $st_i$ 不再是 单调递增 的了

我们再来观察一下上一篇中推导的公式：

$$ \begin{aligned} &f_i = \min\bigg(f_j + S \times (sc_n - sc_j) + st_i \times (sc_i - sc_j)\bigg) \\\\ 提出常量后的剩余部分：&f_j - sc_j \times (S + st_i) \\\\ 换元：&y - kx \\\\ \end{aligned} $$

此处的换元是令 $\begin{cases} f_j = y_j \\\ sc_j = x_j \\\ k_i = S+st_i \end{cases}$

在 上一篇题解 中提到过，点集 上第一个出现在直线 $y=kx+b$ 上的点是 下凸壳 上的点

且满足 $k_{j-1, j} \le k_i \lt k_{j,j+1}$

下凸壳 上的点集，相邻两点 构成的 斜率 是 单调递增 的

在上题中，斜率 $k(k_i=S+st_i)$ 也是 单调递增 的，故可以用 单调队列 在 队头 维护 大于 $k$ 的 最小值

而本题中，$k_i$ 不具备 单调性，因此不能再用 单调队列 优化了

不过， “下凸壳上的点集，相邻两点构成的斜率是单调递增的”

我们可以利用上 单调性，维护一个 下凸壳的点集，则对于 $k_i$，找到 大于他的最小值 就可以 二分 啦

通过利用一个 队列（非 滑动窗口，故不考虑队列最大长度），完成对于 下凸壳点集 的维护即可

关于如何利用 队列 维护 下凸壳的点集，这在上篇题解中的最后有提到，直接 引用原文 了：

把点插入 队列 前，先要 队列 中 至少有两个点，然后把 满足 $k_{q_{tt-1}~,~q_{tt}} \ge k_{q_{tt}~,~i}$ 的 点 $q_{tt}$ 弹出

即 新加入的点，必须和 原点集 构成 下凸壳，无效点要先删去

这里我把公式展开，方便大家理解：

$$ k_{q_{tt-1}~,~q_{tt}} \lt k_{q_{tt}~,~i} \Rightarrow \frac{y_{q_{tt}}-y_{tt-1}}{x_{q_{tt}}-x_{tt-1}} \lt \frac{y_{i}-y_{tt}}{x_{q_{i}}-x_{tt}} \Rightarrow \frac{f_{q_{tt}}-f_{tt-1}}{sc_{q_{tt}}-sc_{tt-1}} \lt \frac{f_{i}-f_{tt}}{sc_{q_{i}}-sc_{tt}} $$

这样，队列 中 相邻两点 之间构成的直线 斜率单增，也就是我们的 有效下凸壳点集

总结一下本题要点：

1. 用队列维护 下凸壳点集
2. 用 二分 找出 点集 中第一个出现在直线上的点

Code

时间复杂度：$O(n\log n)$

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

using namespace std;

typedef long long LL;

const int N = 3e5 + 10;

int n;
LL S, sc[N], st[N], f[N], que[N];

int main()
{
    scanf("%d%lld", &n, &S);
    for (int i = 1; i <= n; i ++ )
    {
        scanf("%lld%lld", &st[i], &sc[i]);
        st[i] += st[i - 1], sc[i] += sc[i - 1];
    }
    int tt = 0;
    for (int i = 1; i <= n; i ++ )
    {
        int l = 0, r = tt;
        while (l < r)
        {
            int mid = (l + r) >> 1;
            if (f[que[mid + 1]] - f[que[mid]] > 
               (S + st[i]) * (sc[que[mid + 1]] - sc[que[mid]])) r = mid;
            else l = mid + 1;
        }
        f[i] = f[que[r]] + S * (sc[n] - sc[que[r]]) + st[i] * (sc[i] - sc[que[r]]);
        while (tt && (double)(f[que[tt]] - f[que[tt - 1]]) * (sc[i] - sc[que[tt]]) >= 
                     (double)(f[i] - f[que[tt]]) * (sc[que[tt]] - sc[que[tt - 1]]))
            tt -- ;
        que[ ++ tt] = i;
    }
    printf("%lld\n", f[n]);
    return 0;
}