有向直线2中值问题
时间： 1ms 内存：64M
描述：
给定一条有向直线L以及L上的n+1个点x0 < x1 < …… < xn。有向直线L上的每个点xi都有一个权w(xi)；每条有向边(xi,xi-1)也都有一个非负边长d(xi,xi-1)。有向直线L上的每个点xi可以看作客户，其服务需求量为w(xi)。每条边(xi,xi-1)的边长d(xi,xi-1)可以看作运输费用。如果在点xi处未设置服务机构，则将点xi处的服务需求沿有向边转移到点xj处服务机构需付出的服务转移费用为w(xi)*d(xi,xj)。在点x0处已设置了服务机构，现在要在直线L上增设2处服务机构，使得整体服务转移费用最小。对于给定的有向直线L，计算在直线L上增设2处服务机构的最小服务转移费用。
输入：
输入数据的第1行有1个正整数n(n≤20000)，表示有向直线L上除了点x0外还有n个点x0 < x1 < ……< xn。接下来的n行中，每行有2个整数。第i+1行的2个整数分别表示w(xn-i-1)和d(xn-i-1,xn-i-2)。
输出：
输出只有一个整数，表示最小服务转移费用。
示例输入：
9
1 2
2 1
3 3
1 1
3 2
1 6
2 1
1 2
1 1示例输出：
26提示：
参考答案：
解锁文章
诗酒趁年华
援军
老董
翔哥奇思妙想
千千
范明明
深海小涛
简忆工具箱
文章评论