Preparing NOJ

有向直线k中值问题

1000ms 65536K

Description:

给定一条有向直线L以及L上的n+1个点x0 < x1 <...< xn。有向直线L上的每个点都有一个权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上增设k处服务机构,使得整体服务转移费用最小。

对于给定的有向直线L,编程计算在直线L上增设k处服务机构的最小服务转移费用。

Input:

 输入的第1行有1个正整数n,表示有向直线L上除了点x0外还有n个点 x0 < x1 <…< xn 。接下来的n行中,每行有2个整数。第i+1行的2个整数分别表示w(x n-i-1)d(xn-i-1,xn-i-2)

Output:

输出计算的最小服务转移费用。

Sample Input:

9 2
1 2
2 1
3 3
1 1
3 2
1 6
2 1
1 2
1 1

Sample Output:

26

Note:

undefined

本题由旧版NOJ导入,来源:算法设计与实验题解

Info

NOJ

Provider NOJ

Code NOJ1242

Tags

Submitted 0

Passed 0

AC Rate 0%

Date 04/20/2019 10:03:10

Related

Nothing Yet