0%

「洛谷P2365」任务安排 - 斜率优化DP

这题本身挺水的,$n$ 只有 $5000$,不过这题能用斜率规划 $O(n)$ 做,正好在这总结一下斜率规划。


题意

Luogu

题解

斜率规划

斜率规划能够优化形如 $f(i) = \min \limits_{j=1}^{i-1} \left\{a[i]\times x(j)+b[i]\times y(j)\right\}$ 的 DP 方程。其中 $a[i]$,$b[i]$ 是只与 $i$ 有关的常数,$x(j)$,$y(j)$ 是可以由 $f(j)$ 在常数时间内确定的函数。

我们以 $x(i)$ 为横轴,$y(i)$ 为纵轴建立坐标系,则我们的目标为:

$\min P = ax + by$ ,其中 $a = a[i]$,$b = b[i]$

然后化为 $y = -\dfrac{a}{b}x+\dfrac{P}{b}$,我们的任务则是最小化这条直线的纵截距。

画些图模拟一下,我们可以得到这样一个性质:所有最优决策点都在平面点集的凸包上

以最小化为例,一条直线从下往上移动,遇到的第一个点即为答案,则三个点一定不会形成上凸的情况。

此时,根据 $x(i)$ 与斜率的单调性,会有如下三种情况:

情况一:$x(i)$ 与斜率同时具有单调性

我们可以用一个单调队列来维护凸包。以最小化为例,我们要维护一个下凸包,由于斜率是单调的,所以决策点也必然在凸壳上单调移动。当新加入的点的斜率小于原先队尾的斜率,让队尾出队。查询时,若队首斜率小于查询的直线斜率,让队首出队。

情况二:$x(i)$ 单调,斜率不单调

由于斜率不单调,我们可以在凸壳上二分寻找决策点。

情况三:$x(i)$ 与斜率均不具有单调性

这种情况下,可以用二叉平衡树或 CDQ 分治维护凸包。

本题

设 $f_i$ 表示前 $n$ 个任务的最小花费。

转移: $f_i = min\left(f_j + s\times (c_n-c_j) + t_i\times (c_i - c_j)\right)$

化简一下:$f_j=(s+t_i)\times c_j+f_i-s\times c_n-t_i\times c_i$

令 $x(i)=c_i$,$y(i)=f_i$,$a[i]=s+t_i$,$b_i=f_i-s\times c_n-t_i\times c_i$,这就变成了标准的斜率优化形式。

$x(i)$ 和斜率均单增,因此可以直接用单调队列维护。


Code

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
const int N = 5000 + 5;

int n, s, t[N], c[N], f[N];

int x(int i) { return c[i]; }
int y(int i) { return f[i]; }
int a(int i) { return s + t[i]; }
int b(int i) { return f[i] - s * c[n] - t[i] * c[i]; }

struct Queue
{
int que[N], head, tail;
void init()
{
head = 1, tail = 0;
}
double slope(int i, int j)
{
return 1.0 * (y(i) - y(j)) / (x(i) - x(j));
}
void push(int x)
{
while (head < tail && slope(que[tail], que[tail - 1]) >= slope(que[tail], x)) tail--;
que[++tail] = x;
}
int front(int x)
{
while (head < tail && slope(que[head], que[head + 1]) < x) head++;
return que[head];
}
} Q;

int main()
{
scanf("%d%d", &n, &s);
for (int i = 1; i <= n; i++)
{
scanf("%d%d", &t[i], &c[i]);
t[i] += t[i - 1], c[i] += c[i - 1];
}
Q.init();
Q.push(0);
for (int i = 1; i <= n; i++)
{
int j = Q.front(s + t[i]);
f[i] = f[j] + s * (c[n] - c[j]) + t[i] * (c[i] - c[j]);
Q.push(i);
}
printf("%d\n", f[n]);
return 0;
}