stdKonjac's Blog

An AC a day keeps the WA away ~

【工作】

题目描述

这次故事的主角是HG!转眼4年过去了,HG本科毕业了,于是找了份工作。每天HG会收到一份任务清单,清单上列出了 n 个可能需要他完成的任务。每个任务包含 3 个信息:Ti、Ai、Bi,其中 T表示完成此任务需要的时间,A表示此任务的到达时间,B表示此任务的最晚完成时间。在某一时刻若HG手上没有任务,那么他可以选择一个已经到达且还能够在 Bi 时刻之前(或者恰好在 Bi 时刻)完成的任务来做。

注意:B时刻不做工作,必须在 B之前完成。

由于HG有点懒,他想尽量少的减少他的总工作时间,但是他不能在可以做任务的时候故意不做,那么他该如何挑选任务来做呢?

你的任务就是求出HG的最少工作时间(即总共有多少时间HG在做任务)。

输入格式

第一行一个整数 n 表示任务数。
以下 n 行,每行三个整数 Ti,Ai,B

样例数据1

输入

3

15 0 25

50 0 90

45 15 70

输出

50

输出格式

输出仅一个数,即最少工作时间。

备注

【数据范围】
Ti≥1,0≤Ai,Bi≤1200;
30% 的数据满足:n≤5;
60% 的数据满足:n≤500;
100% 的数据满足:n≤1000。

【说明】
输入数据保证 Bi-Ai 要大于等于 T,且小于 2Ti 。

就是道裸DP,枚举时间看在i时间能否做某个工作即可。

下面是代码:

 

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注

*

This site uses Akismet to reduce spam. Learn how your comment data is processed.