题目描述
在一条直线上有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;
}
|