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

题目描述

斜率优化DP 见：任务安排2【斜率优化DP】

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

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

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

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

分析

对于该类序列，考虑用 动态规划 进行子问题划分求解再合并集合

如何进行状态表示:

状态表示-集合 $f_{i,j}$：考虑前 $i$ 个 任务，且当前第 $i$ 个 任务 是第 $j$ 个 批次 的 最后一个任务 的 方案

状态表示-属性 $f_{i,j}$：方案的贡献 最小 $Min$

转移方程：

$$f_{i,j} = \min\bigg({ f_{k, j - 1} + (S \times j + \sum_{u = 1}^i t_u) \times \sum_{u = k + 1}^i c_u }\bigg)$$

两维状态 套一个 决策变量，时间复杂度为 $O(n^3)$

这里 蓝书 上用了一个 经典的优化思想： 费用提前计算 思想

题目中并没有说，我们 至多 只能够把任务分成 $k$ 批次，可是在 DP 中我们却人为的引入了参数 $j$，仅仅只是因为我们在计算 当前状态 时，需要知道 $S$ 对于 该批次 $j$ 的 贡献：$Scost_{j} = S \times j$

然而，比起 $j$ 对 $f_i$ 的 影响，我们 实际上 关心的是 $S$ 对 $f_i$ 的 影响

$j$ 是为了求出 $S$ 对 $f_i$ 的影响，而被我们额外引入的参数

若当前为 $[l, r]$ 的 任务 开一个新 批次，那么 该批次 机器的 启动时间 $S$ 会 影响 的 任务 有 $[l, n]$

那么，我们不妨用 费用提前计算 思想，把该段 $[l,n]$ 的 $S$ 费用 直接累加到 当前状态 $f_i$ 上 计算

这样，省掉了 一维 状态表示。一维状态+一个决策变量，时间复杂度 为 $O(n^2)$

$$\begin{align} f_i &= \min\bigg({ f_j + S \times \sum_{k=j+1}^n c_k + \sum_{k=1}^i t_k \times \sum_{k=j+1}^i c_k }\bigg) \\\\ 前缀和优化： f_i &= \min\bigg(f_j + S \times (sc_n - sc_j) + st_i \times (sc_i - sc_j)\bigg) \end{align}$$

此处转移方程中，我们分离项后，会出现 $i \times j$ 的项，在前缀中求一个极值，可以用斜率优化DP维护凸包，这些会在下篇题解中提到，本篇题解不会讲解（因为可以水两篇）

Code

#include <iostream>
#include <cstring>

using namespace std;

typedef long long LL;

const int N = 5050;

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

int main()
{
    scanf("%d%d", &n, &S);
    for (int i = 1; i <= n; i ++ )
    {
        scanf("%d%d", &st[i], &sc[i]);
        st[i] += st[i - 1], sc[i] += sc[i - 1];
    }
    memset(f, 0x3f, sizeof f); f[0] = 0;
    for (int i = 1; i <= n; i ++ )
        for (int j = 0; j < i; j ++ )
            f[i] = min(f[i], f[j] + st[i] * (sc[i] - sc[j]) + S * (sc[n] - sc[j]));
    printf("%lld\n", f[n]);
    return 0;
}