斜率优化动态规划

题目描述

在一条直线上有n处地方,从左到右依次编号为1, 2, …, n,每处地方都有一定量的煤,每处地方的单位量煤运送单位距离都需要一定的费用,例如在1处有数量为a的煤,单位量的煤运送单位距离的费用是b,那么把这么多煤一共运送c的距离所需要的费用为abc。现在需要把这n处地方的煤送往加工中心处理,为了使得路径单一,所有地方的煤只能向右边(编号较大的地方的方向)运送,已知第n处的地方已经存在了一个加工中心。为了减少煤运送的费用,在这条路径上最多可以添加k个加工中心,使得总运费最少。问最小的运费是多少?(CEOI 2004改编)

输入
输入数据一共包括4行,第1行输入n和k(2<=n<=10000, 1<=k<=min(200, n-1)),表示n处地方,最多添加k个加工中心。第2行输入n个正整数,表示每个地方的煤总量,第3行输入n个正整数,表示每个地方单位数量单位距离运送的费用。第4行输入n-1个正整数,表示从左到右相邻两个地方的距离。除n以外,所有的数字都<=300。
输出
输出一行一个整数,表示最小的运费。

样例

输入样例 1 
3 1
1 2 3
3 2 1
2 2
输出样例 1
6

题目解答

首先我们想到这是一道DP题目,方程为:dp[k][n] = min{0 <= i < n} (dp[k - 1][i] + delta(i + 1, n)) 其中delta(i + 1, n)表示为从i + 1到n的所有树木运送到第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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include<vector>
#define MIN(a, b) (a < b ? a : b)

long k, n, value[10005], dist[10005], f[10005][205];

long DeltaY(int p, int s, int o) {
return (f[p][o] - f[p][0] + value[p] * dist[p]) - (f[s][o] - f[s][0] + value[s] * dist[s]);
}

long DeltaX(int p, int s) {
return value[p] - value[s];
}

int main(){
cin >> n >> k;
for (int i = 1; i <= n; i++) {
cin >> value[i];
}

for (int i = 1; i <= n; i++) {
cin >> value[10004];
value[i] = value[10004] * value[i] + value[i - 1];
}

for (int i = 2; i <= n; i++) {
cin >> dist[i];
dist[i] += dist[i - 1];
for (int j = 1; j <= i; j++) {
f[i][0] += (value[j] - value[j - 1]) * (dist[i] - dist[j]);
}
}

for (int s = 1; s <= k + 1; s++) {
int head = 0, tail = 0;
vector<int> q(n + 1);
for (int i = s; i <= n; i++) {
int o = s - 1;
while(head < tail && DeltaY(q[head + 1], q[head], o) <= DeltaX(q[head + 1], q[head]) * dist[i])
head++;
f[i][s] = f[q[head]][o] + f[i][0] - f[q[head]][0] - value[q[head]] * (dist[i] - dist[q[head]]);

while(head < tail && DeltaY(i, q[tail], o) * DeltaX(q[tail], q[tail - 1]) <= DeltaY(q[tail], q[tail - 1], o) * DeltaX(i, q[tail]))
tail--;

q[++tail] = i;
}
}

cout << f[n][k] << endl;
return 0;
}