Preparing NOJ

直线k中值问题

1000ms 65536K

Description:

在一个按照南北方向划分成规整街区的城市里,n个居民点分布在一条直线上的n个坐标点x1<...<xn处。居民们希望在城市中至少选择1个,但不超过k个居民点建立服务机构。在每个居民点xi处,服务需求量为wi0,在该居民点设置服务机构的费用为ci0。假设居民点xi到距其最近的服务机构的距离为di,则居民点xi的服务费用为wi´di。建立k个服务机构的总费用为A+BA是在k个居民点设置服务机构的费用的总和;Bn个居民点服务费用的总和。

对于给定直线L上的n个点x1<...<xn,编程计算在直线L上最多设置k处服务机构的最小总费用。

Input:

输入的第1行有2个正整数nkn表示直线L上有n个点x1<...<xnk是服务机构总数的上限。接下来的n行中,每行有3个整数。第i+1行的3个整数xi,wi,ci,分别表示相应居民点的位置坐标,服务需求量和在该点设置服务机构的费用。

Output:

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

Sample Input:

9 3
2 1 2
3 2 1
6 3 3
7 1 1
9 3 2
15 1 6
16 2 1
18 1 2
19 1 1

Sample Output:

19

Note:

undefined

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

Info

NOJ

Provider NOJ

Code NOJ1245

Tags

Submitted 3

Passed 1

AC Rate 33.33%

Date 04/20/2019 10:03:10

Related

Nothing Yet