P2064 - [蓝桥杯2022初赛] 红绿灯

内存限制：256 MB 时间限制：1 S 标准输入输出

题目类型：传统评测方式：文本比较上传者：

提交：12 通过：5

爱丽丝要开车去上班，上班的路上有许多红绿灯，这让爱丽丝很难过。
为了上班不迟到，她给自己的车安装了氮气喷射装置。现在她想知道自己上班最短需要多少时间。
爱丽丝的车最高速度是1/V米每秒，并且经过改装后，可以瞬间加速到小于等于最高速的任意速度，也可以瞬间停止。
爱丽丝家离公司有N米远，路上有M个红绿灯，第i个红绿灯位于离爱丽丝家Ai米远的位置，绿灯持续Bi秒，红灯持续Ci秒。
在初始时（爱丽丝开始计时的瞬间），所有红绿灯都恰好从红灯变为绿灯。
如果爱丽丝在绿灯变红的瞬间到达红绿灯，她会停下车等红灯，因为她是遵纪守法的好市民。
氮气喷射装置可以让爱丽丝的车瞬间加速到超光速（且不受相对论效应的影响！），达到瞬移的效果。
但是爱丽丝是遵纪守法的好市民，在每个红绿灯前她都会停下氮气喷射。
即使是绿灯，因为红绿灯处有斑马线，而使用氮气喷射装置通过斑马线是违法的。
此外，氮气喷射装置不能连续启动，需要一定时间的冷却，表现为通过K 个红绿灯后才能再次使用。
（也就是说，如果K = 1，就能一直使用啦！）
初始时，氮气喷射装置处于可用状态。

第一行四个正整数N、M、K、V，含义如题面所述。
接下来M 行，每行三个正整数Ai、Bi、Ci，含义如题面所述。
对于30% 的数据，N≤100, M≤10, M ＜ K, V ＝ 1.
对于60% 的数据，N≤1000, M≤100, K≤50, Bi,Ci≤100, V≤10.
对于100% 的数据，0＜N≤10^8, M≤1000; K≤1000; 0＜Bi,Ci≤10^6, 0＜V≤10^6, 0＜Ai＜N。
对任意i＜j, 有Ai＜Aj。

输出一个正整数T，表示爱丽丝到达公司最短需要多少秒。

90 2 2 2
30 20 20
60 20 20

爱丽丝在最开始直接使用氮气喷射装置瞬间到达第一个红绿灯，
然后绿灯通过，以最高速行进60 秒后到达第二个红绿灯，此时绿灯刚好变红，
于是她等待20 秒再次变为绿灯后通过该红绿灯，此时氮气喷射装置冷却完毕，
爱丽丝再次使用瞬间到达公司，总共用时80 秒。

进阶题动态规划

2064: [蓝桥杯2022初赛] 红绿灯

题目描述

输入格式

输出格式

输入样例复制

输出样例复制

数据范围与提示

分类标签