/ JoyAc / 题库 /

种树

种树

测试数据来自 wjszez/2007

题目描述
 一条街的一边有几座房子。因为环保原因居民想要在路边种些树。路边的地区被分割成块,并被编号成1..N。每个部分为一个单位尺寸大小并最多可种一棵树。每个居民想在门前种些树并指定了三个号码B,E,T。这三个数表示该居民想在B和E之间最少种T棵树。当然,B≤E,居民必须记住在指定区不能种多于区域地块数的树,所以T≤E-B+l。居民们想种树的各自区域可以交叉。你的任务是求出能满足所有要求的最少的树的数量。
写一个程序计算最少要种树的数量。
输入
第一行包含数据N,区域的个数(0<N≤30000);
第二行包含H,房子的数目(0<H≤5000);
下面的H行描述居民们的需要:B E T,0<B≤E≤30000,T≤E-B+1。
输出
树的数目。
输入样例
9
4
1 4 2
4 6 2
8 9 2
3 5 2
输出样例
5

信息

ID
1088
难度
10
分类
(无)
标签
递交数
1
已通过
0
通过率
0%
上传者

相关

在下列训练计划中:

JoyAc官方训练计划