参考《算法竞赛进阶指南》、AcWing题库

在上一节末尾我们给出了动态规划的一个经典模型 F[i]=min⁡L(i)≤j≤R(i){F[j]+F[i]=\min _{L(i) \leq j \leq R(i)}\{F[j]+ val⁡(i,j)}\operatorname{val}(i, j)\}, 并总结了单调队列优化的基本条件一一多项式 val⁡(i,j)\operatorname{val}(i, j) 的每一项仅与 ii 和 jj 中的一个有关。在本节中, 我们将讨论多项式 val⁡(i,j)\operatorname{val}(i, j) 包含 i,ji, j 的乘积项, 即存在一个同时与 ii 和 jj 有关的部分时, 该如何进行优化。

300. 任务安排1

题目描述

有 NN 个任务排成一个序列在一台机器上等待执行，它们的顺序不得改变。

机器会把这 NN 个任务分成若干批，每一批包含连续的若干个任务。

从时刻 00 开始，任务被分批加工，执行第 ii 个任务所需的时间是 TiT_i。

另外，在每批任务开始前，机器需要 SS 的启动时间，故执行一批任务所需的时间是启动时间 SS 加上每个任务所需时间之和。

一个任务执行后，将在机器中稍作等待，直至该批任务全部执行完毕。

也就是说，同一批任务将在同一时刻完成。

每个任务的费用是它的完成时刻乘以一个费用系数 CiC_i。

请为机器规划一个分组方案，使得总费用最小。

输入格式

第一行包含整数 NN。

第二行包含整数 SS。

接下来 NN 行每行有一对整数，分别为 TiT_i 和 CiC_i，表示第 ii 个任务单独完成所需的时间 TiT_i 及其费用系数 CiC_i。

输出格式

输出一个整数，表示最小总费用。

数据范围

1≤N≤50001 \le N \le 5000,
0≤S≤500 \le S \le 50,
1≤Ti,Ci≤1001 \le T_i,C_i \le 100

输入样例：

1
2
3
4
5
6
7
5
1
1 3
3 2
4 3
2 3
1 4

输出样例：

1
153

算法分析

解法一

求出 T,CT, C 的前缀和 sum⁡T,sum⁡C\operatorname{sum} T, \operatorname{sum} C, 即 sum⁡T[i]=∑j=1iT[j],sumC⁡[i]=∑j=1iC[j]\operatorname{sum} T[i]=\sum_{j=1}^{i} T[j], \operatorname{sumC}[i]=\sum_{j=1}^{i} C[j] 。 设 F[i,j]F[i, j] 表示把前 ii 个任务分成 jj 批执行的最小费用, 则第 jj 批任务完成的时间就是 j∗S+sumT[i]j * S+s u m T[i] 。以第 j−1j-1 批和第 jj 批任务的分界点为 DP 的 “决策” , 状态转移方程为:

F[i,j]=min⁡0≤k<i{F[k,j−1]+(S∗j+sumT[i])∗(sumC[i]−sumC[k])}F[i, j]=\min _{0 \leq k<i}\{F[k, j-1]+(S * j+s u m T[i]) *(s u m C[i]-s u m C[k])\}

该解法的时间复杂度为 O(N3)O\left(N^{3}\right) 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define ll long long
using namespace std;
const int N = 5006;
const ll INF = 0x3f3f3f3f3f3f3f3fll;
int n;
ll s, st[N], sc[N], f[N][N];

int main() {
	cin >> 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];
	}
	memset(f, 0x3f, sizeof(f));
	f[0][0] = 0;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= i; j++)
			for (int k = 0; k < i; k++)
				f[i][j] = min(f[i][j], f[k][j-1] + (s * j + st[i]) * (sc[i] - sc[k]));
	ll ans = INF;
	for (int i = 1; i <= n; i++)
		ans = min(ans, f[n][i]);
	cout << ans << endl;
	return 0;
}
解法二

本题并没有规定需要把任务分成多少批, 在上一个解法中之所以需要批数 jj, 是因为我们需要知道机器启动了多少次 (每次启动都要 SS 单位时间), 从而计算出 ii 所在的一批任务的完成时刻。

事实上, 在执行一批任务时, 我们不容易直接得知在此之前机器启动过几次。但我们知道, 机器因执行这批任务而花费的启动时间 SS, 会累加到在此之后所有任务的完成时刻上。设 F[i]F[i] 表示把前 ii 个任务分成若干批执行的最小费用, 状态转移方程为:

F[i]=min⁡0≤j<i{F[j]+sum⁡T[i]∗( sumC [i]−sumC[j])+s∗(sumC[N]−sumC[j])}F[i]=\min _{0 \leq j<i}\{F[j]+\operatorname{sum} T[i] *(\text { sumC }[i]-s u m C[j])+s *(s u m C[N]-s u m C[j])\}

在上式中, 第 j+1∼ij+1 \sim i 个任务在同一批内完成, sumT[i]s u m T[i] 是忽略机器的启动时间时, 这批任务的完成时刻。因为这批任务的执行, 机器的启动时间 SS 会对第 j+1j+1 个之后的所有任务产生影响, 故我们把这部分补充到费用中。

也就是说，我们没有直接求出每批任务的完成时刻, 而是在一批任务 “开始” 对后续任务产生影响时, 就先把费用累加到答案中。这是一种名为 “费用提前计算” 的经典思想。

该解法的时间复杂度为 O(N2)O\left(N^{2}\right) 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define ll long long
using namespace std;
const int N = 5006;
int n, s;
ll f[N], st[N], sc[N];

int main() {
	cin >> 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];
	}
	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]));
	cout << f[n] << endl;
	return 0;
}

Solution

301. 任务安排2

题目描述

有 NN 个任务排成一个序列在一台机器上等待执行，它们的顺序不得改变。

机器会把这 NN 个任务分成若干批，每一批包含连续的若干个任务。

从时刻 00 开始，任务被分批加工，执行第 ii 个任务所需的时间是 TiT_i。

另外，在每批任务开始前，机器需要 SS 的启动时间，故执行一批任务所需的时间是启动时间 SS 加上每个任务所需时间之和。

一个任务执行后，将在机器中稍作等待，直至该批任务全部执行完毕。

也就是说，同一批任务将在同一时刻完成。

每个任务的费用是它的完成时刻乘以一个费用系数 CiC_i。

请为机器规划一个分组方案，使得总费用最小。

输入格式

第一行包含整数 NN。

第二行包含整数 SS。

接下来 NN 行每行有一对整数，分别为 TiT_i 和 CiC_i，表示第 ii 个任务单独完成所需的时间 TiT_i 及其费用系数 CiC_i。

输出格式

输出一个整数，表示最小总费用。

数据范围

1≤N≤3×1051 \le N \le 3 \times 10^5,
1≤Ti,Ci≤5121 \le T_i,C_i \le 512,
0≤S≤5120 \le S \le 512

输入样例：

1
2
3
4
5
6
7
5
1
1 3
3 2
4 3
2 3
1 4

输出样例：

1
153

算法分析

对上一题的解法二进行优化, 先对状态转移方程稍作变形, 把常数、仅与 ii 有关的项、仅与 jj 有关的项以及 i,ji, j 的乘积项分开。

F[i]=min⁡0≤j<i[F[j]−(S+sumT⁡[i])∗sumC⁡[j]}+sumT⁡[i]∗sumC⁡[i]+S∗sumC⁡[N]\begin{aligned} F[i] &=\min _{0 \leq j<i}[F[j]-(S+\operatorname{sumT}[i]) * \operatorname{sumC}[j]\} \\ &+\operatorname{sumT}[i] * \operatorname{sumC}[i]+S * \operatorname{sumC}[N] \end{aligned}

把 min⁡\min 函数去掉, 把关于 jj 的值 F[j]F[j] 和 sumC[j]s u m C[j] 看作变量, 其余部分看作常数, 得到:

F[j]=(S+sum⁡T[i])∗sum⁡C[j]+F[i]−sum⁡T[i]∗sum⁡C[i]−S∗sumC⁡[N]F[j]=(S+\operatorname{sum} T[i]) * \operatorname{sum} C[j]+F[i]-\operatorname{sum} T[i] * \operatorname{sum} C[i]-S * \operatorname{sumC}[N]

在 sum⁡C[j]\operatorname{sum} C[j] 为横坐标, F[j]F[j] 为纵坐标的平面直角坐标系中, 这是一条以 S+S+ sum⁡T[i]\operatorname{sum} T[i] 为斜率, F[i]−sum⁡T[i]∗sumC⁡[i]−S∗sumC⁡[N]F[i]-\operatorname{sum} T[i] * \operatorname{sumC}[i]-S * \operatorname{sumC}[N] 为截距的直线。也就是说, 决策候选集合是坐标系中的一个点集, 每个决策 jj 都对应着坐标系中的一个点 (sumC[j],F[j])(s u m C[j], F[j]) 。每个待求解的状态 F[i]F[i] 都对应着一条直线的截距, 直线的斜率是一 个固定的值 S+sumT⁡[i]S+\operatorname{sumT}[i], 截距末知。当截距最小化时, F[i]F[i] 也取到最小值。

该问题实际上是一个线性规划问题, 高中数学课本中应该有所涉及。令直线过每个决策点 (sumC[j],F[j]sumC[j],F[j]), 都可以解出一个截距, 其中使截距最小的一个就是最优决策。 体现在坐标系中, 就是用一条斜率为固定正整数的直线自下而上平移, 第一次接触到某 个决策点时, 就得到了最小截距。如下图所示:

对于任意三个决策点 (sumC [j1],F[j1]\left[j_{1}\right], F\left[j_{1}\right] ), (sumC [j2],F[j2]\left[j_{2}\right], F\left[j_{2}\right] ) 和 (sumC[j3],F[j3])\left(s u m C\left[j_{3}\right], F\left[j_{3}\right]\right),
不妨设 j1<j2<j3j_{1}<j_{2}<j_{3}, 因为 T,CT, C 均为正整数, 亦有 sum⁡C[j1]<sum⁡C[j2]<sum⁡C[j3]\operatorname{sum} C\left[j_{1}\right]<\operatorname{sum} C\left[j_{2}\right]<\operatorname{sum} C\left[j_{3}\right] 。 根据 “及时排除无用决策” 的思想, 我们来考虑 j2j_{2} 有可能成为最优决策的条件。

从上图中我们发现, j2j_{2} 有可能成为最优决策, 当且仅当:

F[j2]−F[j1]sumC⁡[j2]−sum⁡C[j1]<F[j3]−F[j2]sumC⁡[j3]−sumC⁡[j2]\frac{F\left[j_{2}\right]-F\left[j_{1}\right]}{\operatorname{sumC}\left[j_{2}\right]-\operatorname{sum} C\left[j_{1}\right]}<\frac{F\left[j_{3}\right]-F\left[j_{2}\right]}{\operatorname{sumC}\left[j_{3}\right]-\operatorname{sumC}\left[j_{2}\right]}

不等号两侧实际上都是连接两个决策点的线段的斜率。通俗地讲, 我们应该维护“连接相邻两点的线段斜率” 单调递增的一个 “下凸壳”, 只有这个 “下凸壳” 的顶点才有可能成为最优决策。实际上, 对于一条斜率为 kk 的直线, 若某个顶点左侧线段的斜率比 kk 小、右侧线段的斜率比 kk 大, 则该顶点就是最优决策。换言之, 如果把 这条直线和所有线段组成一个序列, 那么令直线截距最小化的顶点就出现在按照斜率大小排序时, 直线应该排在的位置上。如下图所示:

在本题中, jj 的取值范围是 0≤j<i0 \leq j<i, 随着 ii 的增大, 每次会有一个新的决策进 入候选集合。因为 sumG 的单调性, 新决策在坐标系中的横坐标一定大于之前的所有 决策, 出现在整个凸壳的最右端。另外, 因为 sumTs u m T 的单调性, 每次求解 “最小截距” 的直线斜率 S+sumT[i]S+s u m T[i] 也单调递增, 如果我们只保留凸壳上 “连接相邻两点的线段 斜率” 大于 S+sumT⁡[i]S+\operatorname{sumT}[i] 的部分, 那么凸壳的最左端顶点就一定是最优决策。

综上所述, 我们可以建立单调队列 qq, 维护这个下凸壳。队列中保存若干个决策变 量, 它们对应凸壳上的顶点, 且满足横坐标 sumC 递增、连接相邻两点的线段斜率也 递增。需要支持的操作与一般的单调队列题目类似, 对于每个状态变量 ii :

  1. 检查队头的两个决策变量 q[l]q[l] 和 q[l+1]q[l+1], 若斜率 (F[q[l+1]]−F[q[l]])/(F[q[l+1]]-F[q[l]]) / (sum⁡C[q[l+1]]−sum⁡C[q[l]])≤S+sumT[i](\operatorname{sum} C[q[l+1]]-\operatorname{sum} C[q[l]]) \leq S+s u m T[i], 则把 q[l]q[l] 出队, 继续检查新的队头。
  2. 直接取队头 j=q[l]j=q[l] 为最优决策, 执行状态转移, 计算出 F[i]F[i] 。
  3. 把新决策 ii 从队尾插入, 在插入之前, 若三个决策点 j1=q[r−1],j2=j_{1}=q[r-1], j_{2}= q[r],j3=iq[r], j_{3}=i 不满足斜率单调递增 (不满足下凸性, 即 j2j_{2} 是无用决策), 则直接从队尾 把 q[r]q[r] 出队, 继续检查新的队尾。

整个算法的时间复杂度为 O(N)O(N) 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<string>
using namespace std;
long long f[300010], sumt[300010], sumc[300010];
int q[300010], n, s;
int main() {
	cin >> n >> s;
	for (int i = 1; i <= n; i++) {
		int t, c;
		scanf("%d%d", &t, &c);
		sumt[i] = sumt[i - 1] + t;
		sumc[i] = sumc[i - 1] + c;
	}
	memset(f, 0x3f, sizeof(f));
	f[0] = 0;
	int l = 1, r = 1;
	q[1] = 0;
	for (int i = 1; i <= n; i++) {
		while (l < r && (f[q[l + 1]] - f[q[l]]) 
			<= (s + sumt[i]) * (sumc[q[l + 1]] - sumc[q[l]])) l++;
		f[i] = f[q[l]] - (s + sumt[i]) * sumc[q[l]]
			+ sumt[i] * sumc[i] + s * sumc[n];
		while (l < r && (f[q[r]] - f[q[r - 1]]) * (sumc[i] - sumc[q[r]])
			>= (f[i] - f[q[r]]) * (sumc[q[r]] - sumc[q[r - 1]])) r--;
		q[++r] = i;
	}
	cout << f[n] << endl;
}

与一般的单调队列优化 DP 的模型相比, 本题维护的 “单调性” 依赖于队列中相邻 两个元素之间的某种 “比值”。因为这个值对应线性规划的坐标系中的斜率, 所以我们 把本题中使用的优化方法称为 “斜率优化” , 英文称为 convex hull trick (直译为凸壳 优化策略)。

Solution

302. 任务安排3

题目描述

有 NN 个任务排成一个序列在一台机器上等待执行，它们的顺序不得改变。

机器会把这 NN 个任务分成若干批，每一批包含连续的若干个任务。

从时刻 00 开始，任务被分批加工，执行第 ii 个任务所需的时间是 TiT_i。

另外，在每批任务开始前，机器需要 SS 的启动时间，故执行一批任务所需的时间是启动时间 SS 加上每个任务所需时间之和。

一个任务执行后，将在机器中稍作等待，直至该批任务全部执行完毕。

也就是说，同一批任务将在同一时刻完成。

每个任务的费用是它的完成时刻乘以一个费用系数 CiC_i。

请为机器规划一个分组方案，使得总费用最小。

输入格式

第一行包含两个整数 NN 和 SS。

接下来 NN 行每行有一对整数，分别为 TiT_i 和 CiC_i，表示第 ii 个任务单独完成所需的时间 TiT_i 及其费用系数 CiC_i。

输出格式

输出一个整数，表示最小总费用。

数据范围

1≤N≤3×1051 \le N \le 3 \times 10^5,
0≤S,Ci≤5120 \le S,C_i \le 512,
−512≤Ti≤512-512 \le T_i \le 512

输入样例：

1
2
3
4
5
6
5 1
1 3
3 2
4 3
2 3
1 4

输出样例：

1
153

算法分析

与上一题不同的是, 任务的执行时间 TT 可能是负数。这意味着 sumTs u m T 不具有单调性, 从而需要最小化截距的直线的斜率 S+sumT[i]S+s u m T[i] 不具有单调性。所以, 我们不能在单调队列中只保留凸壳上 “连接相邻两点的线段斜率” 大于 S+sumT[i]S+s u m T[i] 的部分, 而是必须维护整个凸壳。这样一来, 我们就不需要在队头把斜率与 S+sumT[i]S+s u m T[i] 比较。队头也不一定是最优决策, 我们可以在单调队列中二分查找, 求出一个位置 p,pp, p 左侧线段的斜率比 S+sum⁡T[i]S+\operatorname{sum} T[i] 小, 右侧线段的斜率比 S+sum⁡T[i]S+\operatorname{sum} T[i] 大, pp 就是最优决策。

队尾维护斜率单调性的方法与上一题相同

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include<iostream>
#include<cstdio>
using namespace std;
long long sumt[300010], sumc[300010], f[300010];
int q[300010], n, s, l, r;

int binary_search(int i, int k)
{
	if (l == r) return q[l];
	int L = l, R = r;
	while (L < R)
	{
		int mid = (L + R) >> 1;
		if (f[q[mid + 1]] - f[q[mid]] <= k *
			(sumc[q[mid + 1]] - sumc[q[mid]])) L = mid + 1; 
		else R = mid;
	}
	return q[L];
}

int main()
{
	cin >> n >> s;
	for (int i = 1; i <= n; i++)
	{
		int t, c;
		scanf("%d%d", &t, &c);
		sumt[i] = sumt[i - 1] + t, sumc[i] = sumc[i - 1] + c;
	}
	l = r = 1, q[1] = 0;
	for (int i = 1; i <= n; i++)
	{
		int p = binary_search(i, s + sumt[i]);
		f[i] = f[p] - (s + sumt[i]) * sumc[p]
			+ sumt[i] * sumc[i] + s * sumc[n];
		while (l < r && (f[q[r]] - f[q[r - 1]]) * (sumc[i] - sumc[q[r]])
			>= (f[i] - f[q[r]]) * (sumc[q[r]] - sumc[q[r - 1]])) r--;
		q[++r] = i;
	}
	cout << f[n] << endl;
}

Solution

303. 运输小猫

题目描述

小 SS 是农场主，他养了 MM 只猫，雇了 PP 位饲养员。

农场中有一条笔直的路，路边有 NN 座山，从 11 到 NN 编号。

第 ii 座山与第 i−1i-1 座山之间的距离为 DiD_i。

饲养员都住在 11 号山。

有一天，猫出去玩。

第 ii 只猫去 HiH_i 号山玩，玩到时刻 TiT_i 停止，然后在原地等饲养员来接。

饲养员们必须回收所有的猫。

每个饲养员沿着路从 11 号山走到 NN 号山，把各座山上已经在等待的猫全部接走。

饲养员在路上行走需要时间，速度为 11 米/单位时间。

饲养员在每座山上接猫的时间可以忽略，可以携带的猫的数量为无穷大。

例如有两座相距为 11 的山，一只猫在 22 号山玩，玩到时刻 33 开始等待。

如果饲养员从 11 号山在时刻 22 或 33 出发，那么他可以接到猫，猫的等待时间为 00 或 11。

而如果他于时刻 11 出发，那么他将于时刻 22 经过 22 号山，不能接到当时仍在玩的猫。

你的任务是规划每个饲养员从 11 号山出发的时间，使得所有猫等待时间的总和尽量小。

饲养员出发的时间可以为负。

输入格式

第一行包含三个整数 N，M，PN，M，P。

第二行包含 n−1n-1 个整数，D2,D3,…,DND_2,D_3,…,D_N。

接下来 MM 行，每行包含两个整数 HiH_i 和 TiT_i。

输出格式

输出一个整数，表示所有猫等待时间的总和的最小值。

数据范围

2≤N≤1052 \le N \le 10^5,
1≤M≤1051 \le M \le 10^5,
1≤P≤1001 \le P \le 100,
1≤Di<10001 \le D_i < 1000,
1≤Hi≤N1 \le H_i \le N,
0≤Ti≤1090 \le T_i \le 10^9

输入样例：

1
2
3
4
5
6
7
8
4 6 2
1 3 5
1 0
2 1
4 9
1 10
2 10
3 12

输出样例：

1
3

算法分析

对于每只猫, 设 Ai=Ti−∑j=1HiDjA_{i}=T_{i}-\sum_{j=1}^{H_{i}} D_{j} 。一名饲养员如果想接到第 ii 只猫, 就必须在 AiA_{i} 时刻之后从 1 号山出发。若出发时刻为 tt, 则这只猫的等待时间就是 t−Ait-A_{i} 。

把 AiA_{i} 从小到大排序, 求出排好序的 AA 数组的前缀和, 记录在数组 SS 中。根据贪 心策略, 每个词养员带走的猫一定是按照 AA 排序后连续的若干只, 请读者尝试给出证 明, 这里就不再㲠述。
此时本题就与 “任务安排” 非常类似。饲养员就是 “机器”, 猫就是 “任务”, 每 个饲养员带走连续的一段猫。设 F[i,j]F[i, j] 表示前 ii 个饲养员带走前 jj 只猫, 猫等待时 间的总和最小是多少。
假设第 ii 个饲养员带走第 k+1∼jk+1 \sim j 只猫, 那么该饲养员的最早出发时间就是 AjA_{j} 。 这些猫的等待时间之和就是 ∑p=k+1j(Aj−Ap)=Aj∗(j−k)−(Sj−Sk)\sum_{p=k+1}^{j}\left(A_{j}-A_{p}\right)=A_{j} *(j-k)-\left(S_{j}-S_{k}\right) 。写出状态转 移方程:

F[i,j]=min⁡0≤k<j{F[i−1,k]+Aj∗(j−k)−(Sj−Sk))}\left.F[i, j]=\min _{0 \leq k<j}\left\{F[i-1, k]+A_{j} *(j-k)-\left(S_{j}-S_{k}\right)\right)\right\}

直接枚举 kk, 求出 F[i,j]F[i, j] 的最小值, 时间复杂度为 O(PM2)O\left(P M^{2}\right) 。

把外层循环 ii 看作定值, jj 是状态变量, kk 是决策变量。方程中存在乘积项 Aj∗A_{j} * kk, 应考虑使用斜率优化。去掉 min⁡\min 函数, 对方程进行移项, 等号左边放仅与 kk 有关 的项, 等号右边放 j,kj, k 乘积项以及仅与 jj 有关的项:

F[i−1,k]+Sk=Aj∗k+F[i,j]−Aj∗j+SjF[i-1, k]+S_{k}=A_{j} * k+F[i, j]-A_{j} * j+S_{j}

以 kk 为横坐标, F[i−1,k]+SkF[i-1, k]+S_{k} 为纵坐标建立平面直角坐标系。上式是一条以 AjA_{j} 为斜率, F[i,j]−Aj∗j+SjF[i, j]-A_{j} * j+S_{j} 为截距的直线, 当截距最小化时, F[i,j]F[i, j] 取到最小值。

在最小化截距的线性规划问题中, 应维护一个下凸壳。建立一个单调队列, 队列中 相邻两个决策 k1k_{1} 和 k2k_{2} 应满足 k1<k2k_{1}<k_{2} 并且 “斜率” ((F[i−1,k2]+Sk2)−(F[i−\left(\left(F\left[i-1, k_{2}\right]+S_{k_{2}}\right)-(F[i-\right. 1,k1]+Sk1))/(k2−k1)\left.\left.\left.1, k_{1}\right]+S_{k_{1}}\right)\right) /\left(k_{2}-k_{1}\right) 单调递增。因为直线斜率 AjA_{j} 也也已经从小到大排过序, 所以在 程序实现中, 采用与 “任务安排 2 ” 类似的单调队列的三个基本操作即可。

Solution