#F0235. #2333. 「JOI 2016/2017 决赛」准高速电车
#2333. 「JOI 2016/2017 决赛」准高速电车
题目描述
题目译自 JOI 2016/2017 本選 T2「準急電車（Semiexpress）」
JOI 铁路公司是 JOI 国唯一的铁路公司。
在某条铁路沿线共有 座车站，依次编号为 。 目前，正在服役的车次按照运行速度可分为两类：高速电车（简称快车）与普通电车（简称慢车）。
- 慢车每站都停。乘慢车时，对于任意一座车站 ，车站 到车站 用时均为 。
- 快车只在车站 停车 。乘快车时，对于任意一座车站 ，车站 到车站 用时均为 。
JOI 铁路公司现拟开设第三类车次：准高速电车（简称准快车）。乘准快车时，对于任意一座车站 ，车站 到车站 用时均为 。准快车的停站点尚未确定，但满足以下条件：
- 快车在哪些站停车，准快车就得在哪些站停车。
- 准快车必须恰好有 个停站点。
JOI 铁路公司希望，在 分钟内（不含换乘时间），车站 可以抵达的车站（不含车站 ）的数量 尽可能多。但是，后经过的车站的编号 必须比 先经过的车站的编号 大。
求出在 分钟内，可抵达车站的最大数目。
输入格式
第一行有三个整数 ，用空格分隔。
第二行有三个整数 ，用空格分隔。
第三行有一个整数 。
在接下来的 行中，第 行有一个整数 。
输入的所有数的含义见题目描述。
输出格式
一行，一个整数，表示在 分钟内，可抵达车站的最大数目。
样例
样例输入 1
10 3 5
10 3 5
30
1
6
10样例输出 1
8样例解释 1
在这组样例中，这条铁路上有 个车站，快车在车站 停车。如果准快车在车站 停车，除车站⑨外的其它所有车站都可在 分钟内到达。
以下是从地点 到达某些站点的最快方案：
- 到达车站 ：乘坐慢车，耗时 分钟。
- 到达车站 ：先乘坐快车，在车站 转慢车，耗时 分钟。
- 到达车站 ：先乘坐快车，在车站 转准快车，耗时 分钟。
- 到达车站⑨：先乘坐快车，在车站 转准快车，在车站 再转慢车，耗时 分钟。
样例输入 2
10 3 5
10 3 5
25
1
6
10样例输出 2
7样例输入 3
90 10 12
100000 1000 10000
10000
1
10
20
30
40
50
60
70
80
90样例输出 3
2样例输入 4
12 3 4
10 1 2
30
1
11
12样例输出 4
8样例输入 5
300 8 16
345678901 123456789 234567890
12345678901
1
10
77
82
137
210
297
300样例输出 5
72样例输入 6
1000000000 2 3000
1000000000 1 2
1000000000
1
1000000000样例输出 6
3000数据范围与提示
对于 的数据，。
对于另外 的数据，。
对于所有数据， 。
题目来源：fps-loj-small-pics.zip；FPS 共享题包，题包内第 126 题。保留原作者与原赛事署名。