引 洛谷 P2365 任务安排#

题目地址：P2365

题目难度：提高+/省选-

个任务排成一个序列在一台机器上等待完成（顺序不得改变），这 个任务被分成若干批，每批包含相邻的若干任务。

从零时刻开始，这些任务被分批加工，第 个任务单独完成所需的时间为 。在每批任务开始前，机器需要启动时间 ，而完成这批任务所需的时间是各个任务需要时间的总和（同一批任务将在同一时刻完成）。

每个任务的费用是它的完成时刻乘以一个费用系数 。请确定一个分组方案，使得总费用最小。

输入格式：

第一行一个正整数 。 第二行是一个整数 。

下面 行每行有一对数，分别为 和 ，表示第 个任务单独完成所需的时间是 及其费用系数 。

输出格式：

一个数，最小的总费用。

数据范围：

对于 的数据，，，。

按照样例最优解给出的图示如上。

根据题目，我们的总花费应是每一组所包含线段的 之和乘上该组的结束时刻（终点在数轴上的横坐标）并求每一组的和。即 。

我们可以发现，最终结果受分组情况的影响。在每一组的开头，均有一段机器的启动时间，它可能会对后期某一组的结束时刻造成影响。有一个技巧，即提前把启动段造成的影响计算出来，而这很明显会牵扯到前缀和的计算。例如下边这个更为普遍的图：

假设 dp[i] 代表将前 个单任务全部分组完毕后的最小花费。在某一时刻，我们已经将前 个任务分成了 两个待处理的区间，并且准备把剩下的 区间划分为一组。分组就涉及到每组起始时的启动时间 。对于已经处理好的 区间，我们有 dp[j] 可以直接拿来调用；对于剩下的待处理区间，我们的总花费是 。其中 项的另一个乘数就代表在此处分组，启动时间 对后边所有的花费带来的影响。因为公式里出现了部分和，因此预处理 的前缀和。

注意到 ，且 ，因此算法是 的。因为数据较小，此方法可以通过，状态转移方程 dp[i] = min(dp[i], dp[j] + sumT[i] * (sumF[i] - sumF[j]) + s * (sumF[n] - sumF[j]))。

AcWing 301 任务安排2#

题目地址：AcWing 301

题目难度：中等

题面相同，本题数据范围扩大到： ，，

状态转移方程与上一题完全相同，我们在这里探讨它的优化方式。

我们的目的是把求解状态的时间复杂度降落到 及以下，首先就需要压缩维度。先从 的循环开始——观察到方程中涉及到 的项有两个：dp[j] 和 sumF[j]。我们将 拆出来，便于简化。得到：

由题目给定，每次循环的 均有一个固定值，因此有关 的项为定值。例如 、。我们成功地把整个算式改造成了更为清爽的形式。联想到直线的斜截式方程： 把转移方程看作这样一个方程，那么斜率 ，截距 。

我们需要最小化 ，显然需要让 最小，因为 。因为直线 过点 ，……相应地，点 等也在这条直线上，问题再度简化为：“对于每次变化的斜率，找出一个点，使得当前直线截距最小”。

可以发现，无论直线的斜率再怎么变动，能让截距取得最值的那个点从始至终都是下边的那几个。事实上，对于斜率为 的直线，让它取得最值的点都是第一个斜率比 大的点。剩下的点就完全是鸡肋了。

二维凸包是指内角均在 范围内的凸多边形，相当于用一个橡皮筋围住一些固定的大头针，橡皮筋围出来的图形就是一个凸包。因为橡皮筋总是自发地向周长减小的方向去收缩，因而凸包在周长上具有优势。在上图中，红色线连出来的就是一个凸包的下边界。从左至右，每两个点连线的斜率是单调递增的，且直线倾斜角小于 。这启发我们把下边界上的每个点的斜率统计出来，然后组成一个斜率单调递增的点序列，对于每条直线，在序列中找到第一个斜率大于当前直线斜率的点即可，从而想到使用 upper_bound 或者是二分解决。

在本题中，有一些奇妙的性质。这些性质允许我们不使用二分，而是直接 查询合法解：

1. 均为正整数，对于它们的前缀和显然也如此。循环 时， 是单调递增的。
2. 每次新加入一个点 时，由于如上的单调性，点的横坐标是单调递增的。

因此我们在查询时，把队头斜率小于当前斜率的点弹出；插入时把队尾不在凸包上的点删去，其实就是让新读取的点代替原先的点。定量来说，就是：当 时弹出点 ；当 时弹出队尾点（代码中常用交叉相乘避免除法精度问题，但需要开 long long）。循环时只需要把 设置成符合要求的凸包上的点就行了。以上其实也是 扫描法维护凸包的核心思想。因为涉及到队列中非首尾元素的访问，故使用数组模拟。

1
#include <bits/stdc++.h>
2
#define N 300010
3
using namespace std;
4

5
typedef long long ll;
6

7
ll dp[N];
8
ll f[N], t[N];
9
int q[N];
10

11
int main() {
12
    ios::sync_with_stdio(false);
13
    cin.tie(nullptr);
14
    cout.tie(nullptr);
15

16
    int n, s;
17
    cin >> n >> s;
18
    for (int i = 1; i <= n; i++) {
19
        cin >> t[i] >> f[i];
20
        f[i] += f[i - 1];
21
        t[i] += t[i - 1];
22
    }
23
    int hh = 0, tt = 0;
24
    q[0] = 0;
25
    for (int i = 1; i <= n; i++) {
26
        while (hh < tt && (dp[q[hh + 1]] - dp[q[hh]]) <= (t[i] + s) * (f[q[hh + 1]] - f[q[hh]])) hh++;
27
        int j = q[hh];
28
        dp[i] = dp[j] - (t[i] + s) * f[j] + f[i] * t[i] + s * f[n];
29
        while (hh < tt && (dp[q[tt]] - dp[q[tt - 1]]) * (f[i] - f[q[tt]]) >= (dp[i] - dp[q[tt]]) * (f[q[tt]] - f[q[tt - 1]])) tt--;
30
        q[++tt] = i;
31
    }
32
    cout << dp[n] << endl;
33
    return 0;
34
}

洛谷 P5785 [SDOI2012] 任务安排/AcWing 302 任务安排3#

题目地址：P5785/AcWing 302

题目难度：省选/NOI-/困难

题目来源：山东  2012  各省省选

题面相同，数据范围中 可能为负数。

为负数，代表它的前缀和，或者更进一步—— 不再单调递增。此时使用单调队列维护凸包的思路就不再正确。但是考虑到我们要求大于当前斜率且斜率相对最小的点（最大的最小），考虑二分。

需要注意的是，尽管待求直线的斜率 失去了单调性，但是凸包的基本性质并没改变，下凸包相邻两点构成的斜率还是单调递增的。因此继续用队列维护凸包，这时只需维护点是否在凸包上，即不满足要求时弹出队尾。对于每次 的输入，都二分出一个斜率大于它且最接近它的凸包点，把 赋值过去就完成了（把 int j = q[hh] 替换成二分查找）。

由于本题数据较大，在交叉相乘时可能会爆，因此推荐使用 double 或 __int128。

1
#include <bits/stdc++.h>
2
#define N 300010
3
using namespace std;
4

5
typedef long long ll;
6

7
ll dp[N];
8
ll f[N], t[N];
9
int tt = 0;
10
int q[N];
11

12
int upperbound(ll piv) {
13
    int L = 0, R = tt;
14
    while (L < R) {
15
        int mid = (L + R) >> 1;
16
        if ((__int128) (dp[q[mid + 1]] - dp[q[mid]]) > (__int128) (f[q[mid + 1]] - f[q[mid]]) * piv) R = mid;
17
        else L = mid + 1;
18
    }
19
    return q[L];
20
}
21

22
int main() {
23
    ios::sync_with_stdio(false);
24
    cin.tie(nullptr);
25
    cout.tie(nullptr);
26

27
    int n, s;
28
    cin >> n >> s;
29
    for (int i = 1; i <= n; i++) {
30
        cin >> t[i] >> f[i];
31
        t[i] += t[i - 1];
32
        f[i] += f[i - 1];
33
    }
34
    q[0] = 0;
35
    for (int i = 1; i <= n; i++) {
36
        int j = upperbound(t[i] + s);
37
        dp[i] = dp[j] - (t[i] + s) * f[j] + f[i] * t[i] + s * f[n];
38
        while (tt && (__int128) (dp[q[tt]] - dp[q[tt - 1]]) * (f[i] - f[q[tt]]) >= (__int128) (dp[i] - dp[q[tt]]) * (f[q[tt]] - f[q[tt - 1]])) tt--;
39
        q[++tt] = i;
40
    }
41
    cout << dp[n] << endl;
42
    return 0;
43
}

CF 311B Cats Transport#

题目地址：CF 311B

题目难度：省选/NOI-

Zxr960115 是一个大农场主。

他养了 只可爱的猫子,雇佣了 个铲屎官。这里有一条又直又长的道路穿过了农场，有 个山丘坐落在道路周围，编号自左往右从 到 。山丘 与山丘 的距离是 米。铲屎官们住在 号山丘。

一天，猫子们外出玩耍。猫子 去山丘 游玩，在 时间结束他的游玩，然后在山丘 傻等铲屎官。铲屎官们必须把所有的猫子带上。每个铲屎官直接从 走到 ，中间不停下，可以认为不花费时间的把游玩结束的猫子带上。每个铲屎官的速度为一米每单位时间，并且足够强壮来带上任意数量的猫子。

举个栗子，假装我们有两个山丘( )，有一只猫子，他想去山丘 玩到时间 。然后铲屎官如果在时间 或者时间 从 号山丘出发，他就能抱走猫子。如果他在时间 出发那么就不行(猫子还在玩耍)。如果铲屎官在时间 出发，猫子就不用等他（）。如果他在时间 出发，猫子就要等他 个单位时间。

你的任务是安排每个铲屎官出发的时间(可以从 0 时刻之前出发），最小化猫子们等待的时间之和。

对于全部的数据，满足 ，，，，，。

输入格式：

输入的第一行是三个整数 。

第二行有 个整数，分别是 。

接下来 行，每行两个整数 。

输出格式：

一行一个整数，为最小化的等待时间之和。

在本题中，请务必使用 cin/cout 或者 %I64d 通配符来读入64位整数。

读题就能发现，我们的饲养员的行走时间和 的前缀和有关，因此预处理出来，重定义 。根据题意我们知道，当饲养员的出发时间早于或等于 时，都等价于 （刚好接到，毕竟干等着猫玩完的那一刻再接回去也是一样的），可以看作是饲养员出发时间的下限。更普遍地，假设 饲养员出发的时间为 ，就有 。

接下来的转换非常巧妙：定义 ，即最早出发时间。按照 升序排序获得一个新的序列，我们试着把排序后的山分组，使得总等待时间最小。看上去就有点《任务安排》三部曲的意思了。

假如我们的饲养员想要一次性接完排序 的小猫，他的最早出发时间就是 ， 号总的等待时间就是 （）。普遍规律就是：

这道题还有一个硬性要求——饲养员的个数不超过 ，因此开两维动态规划数组 dp[i][j] 表示使用了 名饲养员去接前 只小猫的最小等待时长总和。在 范围内，用中间变量 分隔开：对于 ，它的最小值就是 dp[k][j - 1]，那么我们派出第 名饲养员去接小猫 ，造成的花费是 。至此这道题完全转化为了《任务安排》三部曲。状态转移方程为：dp[i][j] = min(dp[i][j], dp[k][j - 1] + (i - k) * a[i] - (sumA[i] - sumA[k]))

同样的思路，我们把方程化简成 的形式。原则是把斜率设置成不变量，因此得到：

斜率是 ，注意到当前 是单调递增的，因此沿用单调队列来维护整个凸包。

1
#include <bits/stdc++.h>
2

3
#define N 200010
4
#define P 110
5
using namespace std;
6

7
typedef long long ll;
8

9
int q[N];
10
ll dp[N][P], a[N];
11
ll sumD[N], sumA[N];
12

13
int main() {
14
    ios::sync_with_stdio(false);
15
    cin.tie(nullptr);
16
    cout.tie(nullptr);
17

18
    int n, m, p;
19
    cin >> n >> m >> p;
20
    for (int i = 2; i <= n; i++) {
21
        cin >> sumD[i];
22
        sumD[i] += sumD[i - 1];
23
    }
24
    for (int i = 1; i <= m; i++) {
25
        int h, t;
26
        cin >> h >> t;
27
        a[i] = t - sumD[h];
28
    }
29
    sort(a + 1, a + 1 + m);
30
    for (int i = 1; i <= m; i++) sumA[i] = sumA[i - 1] + a[i];
31

32
    memset(dp, 0x3f, sizeof dp);
33
    for (int i = 0; i <= p; i++) dp[0][i] = 0;
34

35
    for (int j = 1; j <= p; j++) {
36
        int hh = 0, tt = 0;
37
        q[0] = 0;
38
        for (int i = 1; i <= m; i++) {
39
            while (hh < tt && dp[q[hh + 1]][j - 1] + sumA[q[hh + 1]] - dp[q[hh]][j - 1] - sumA[q[hh]] <= a[i] * (q[hh + 1] - q[hh])) hh++;
40
            dp[i][j] = dp[q[hh]][j - 1] + i * a[i] - q[hh] * a[i] - sumA[i] + sumA[q[hh]];
41
            while (hh < tt && (dp[q[tt]][j - 1] + sumA[q[tt]] - dp[q[tt - 1]][j - 1] - sumA[q[tt - 1]]) * (i - q[tt]) >= (dp[i][j - 1] + sumA[i] - dp[q[tt]][j - 1] - sumA[q[tt]]) * (q[tt] - q[tt - 1])) tt--;
42
            q[++tt] = i;
43
        }
44
    }
45
    cout << dp[m][p] << endl;
46
    return 0;
47
}