Preparing NOJ

直线k覆盖问题

1000ms 65536K

Description:

给定一条直线L上的n个点x1<…<xn,每个点xi都有一个权w(i)0,以及在该点设置服务机构的费用c(i)0。每个服务机构的覆盖半径为r。直线k覆盖问题要求找出vn={ x1,x2,…, xn}的一个子集,在点集S处设置服务机构,使总覆盖费用达到最小。直线L上的每个点xi客户。每个点xi到服务机构S的距离定义为。如果客户xiS的服务覆盖范围内,即d(i,s)r,则其服务费用为0,否则其服务费用为w(i)。服务机构S的总覆盖费用为:

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

Input:

输入的第1行有3个正整数nkrn表示直线L上有n个点x1<…<xnk是服务机构总数的上限;r是服务机构的覆盖半径。接下来的n行中,每行有3个整数。第i+1行的3个整数xi , wi , ci,分别表示xi ,w(i)c(i)

Output:

输出计算的最小覆盖费用。

Sample Input:

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

Sample Output:

12

Note:

undefined

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

Info

NOJ

Provider NOJ

Code NOJ1246

Tags

Submitted 0

Passed 0

AC Rate 0%

Date 04/20/2019 10:03:10

Related

Nothing Yet