直线k覆盖问题

Description:

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

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

Input:

输入的第1行有3个正整数n，k和r。n表示直线L上有n个点x₁<…<x_n；k是服务机构总数的上限；r是服务机构的覆盖半径。接下来的n行中，每行有3个整数。第i+1行的3个整数x_i , w_i , c_i，分别表示x_i ,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导入，来源：算法设计与实验题解