![](https://static.youtibao.com/asksite/comm/h5/images/m_q_title.png)
问题描述:在一个按照南北方向划分成规整街区的城市里,n个居民点分布在一条直线上的n个坐标点
![问题描述:在一个按照南北方向划分成规整街区的城市里,n个居民点分布在一条直线上的n个坐标点处.居民们](https://img2.soutiyun.com/ask/2021-01-04/978634507718322.png)
![问题描述:在一个按照南北方向划分成规整街区的城市里,n个居民点分布在一条直线上的n个坐标点处.居民们](https://img2.soutiyun.com/ask/2021-01-04/978634533007768.png)
算法设计:对于给定直线上的n个点,计算在直线L上最多设置k处服务机构的最小总费用.
数据输入:由文件input,txt给出输入数据.第1行有2个正整数n和k.n表示直线L上有n个点k是服务机构总数的上限.接下来的n行中,每行有3个整数.第i+1行的3个整数xi、wi、ci,分别表示相应居民点的位置坐标、服务需求量和在该点设置服务机构的费用.
结果输出:将计算的最小服务费用输出到文件output.txt
![](https://static.youtibao.com/asksite/comm/h5/images/solist_ts.png)