PID569 / Milking Time
题目描述

在一个数轴上可以摆M个线段,每个线段的起始终止端点给定(为整数),且每个线段有一个分值,问如何从中选取一些线段使得任意两个线段之间的距离大于R。每一条线段属于[0,N]。如何选择这些线段,使得分值之和最大?

FROM USACO

输入格式

第一行三个整数,N,M,R。M〈=1000;N〈=1000000

以下M行,每行三个整数,表示起点、终点、分值。

输出格式

一个整数,最大分值。

样例输入
样例输出
提交题目 Error [ 更改语言 ] Language
C C++ Pascal Python2
相关讨论
查看更多讨论
发布新讨论 讨论