HUSTOJ

问题 1256 --#2333. 「JOI 2016/2017 决赛」准高速电车

1256: #2333. 「JOI 2016/2017 决赛」准高速电车

时间限制: 1 Sec 内存限制: 256 MB
提交: 0 解决: 0
[提交][状态][讨论版][命题人:]

题目描述

题目译自 JOI 2016/2017 本選 T2「準急電車（Semiexpress）」

JOI 铁路公司是 JOI 国唯一的铁路公司。

在某条铁路沿线共有 $N$ 座车站，依次编号为 $\ldots, N$ 。目前，正在服役的车次按照运行速度可分为两类：高速电车（简称快车）与普通电车（简称慢车）。

慢车每站都停。乘慢车时，对于任意一座车站 $i(1⩽i<N)i(1\leqslant i<N)$ ，车站 $i$ 到车站 $i + 1$ 用时均为 $A$ 。
快车只在车站 $S1,S2,…,SMS_1, S_2, \ldots, S_M$ 停车 $(1=S1<S2<⋯<SM=N)(1=S_1<S_2<\cdots<S_M=N)$ 。乘快车时，对于任意一座车站 $i(1⩽i<N)i(1\leqslant i<N)$ ，车站 $i$ 到车站 $i + 1$ 用时均为 $B$ 。

JOI 铁路公司现拟开设第三类车次：准高速电车（简称准快车）。乘准快车时，对于任意一座车站 $i(1⩽i<N)i(1\leqslant i<N)$ ，车站 $i$ 到车站 $i + 1$ 用时均为 $C$ 。准快车的停站点尚未确定，但满足以下条件：

快车在哪些站停车，准快车就得在哪些站停车。
准快车必须恰好有 $K$ 个停站点。

JOI 铁路公司希望，在 $T$ 分钟内（不含换乘时间），车站 $1$ 可以抵达的车站（不含车站 $1$ ）的数量尽可能多。但是，后经过的车站的编号必须比先经过的车站的编号大。

求出在 $T$ 分钟内，可抵达车站的最大数目。

第一行有三个整数 $N, M, K$ ，用空格分隔。
第二行有三个整数 $A, B, C$ ，用空格分隔。
第三行有一个整数 $T$ 。
在接下来的 $M$ 行中，第 $i$ 行有一个整数 $S_i$ 。
输入的所有数的含义见题目描述。

一行，一个整数，表示在 $T$ 分钟内，可抵达车站的最大数目。

样例输入 1

样例输出 1

样例解释 1

在这组样例中，这条铁路上有 $10$ 个车站，快车在车站 $1, 6, 10$ 停车。如果准快车在车站 $1, 5, 6, 8, 10$ 停车，除车站⑨外的其它所有车站都可在 $30$ 分钟内到达。
以下是从地点 $1$ 到达某些站点的最快方案：

到达车站 $3$ ：乘坐慢车，耗时 $20$ 分钟。
到达车站 $7$ ：先乘坐快车，在车站 $6$ 转慢车，耗时 $25$ 分钟。
到达车站 $8$ ：先乘坐快车，在车站 $6$ 转准快车，耗时 $25$ 分钟。
到达车站⑨：先乘坐快车，在车站 $6$ 转准快车，在车站 $8$ 再转慢车，耗时 $35$ 分钟。

样例输入 2

样例输出 2

样例输入 3

90 10 12
100000 1000 10000
10000
1
10
20
30
40
50
60
70
80
90

样例输出 3

样例输入 4

样例输出 4

样例输入 5

300 8 16
345678901 123456789 234567890
12345678901
1
10
77
82
137
210
297
300

样例输出 5

样例输入 6

1000000000 2 3000
1000000000 1 2
1000000000
1
1000000000

样例输出 6

对于 $18%18\%$ 的数据， $N⩽300,K−M=2,A⩽106,T⩽109N\leqslant 300, K-M=2, A\leqslant 10^6, T\leqslant 10^9$ 。
对于另外 $30%30\%$ 的数据， $N⩽300N\leqslant 300$ 。
对于所有数据， $1⩽N⩽109,2⩽M⩽K⩽3000,K⩽N,1⩽B<C<A⩽109,1⩽T⩽1018,1\leqslant N\leqslant 10^9, 2\leqslant M\leqslant K\leqslant 3000, K\leqslant N, 1\leqslant B<C<A\leqslant 10^9, 1\leqslant T\leqslant 10^{18},$ $1=S1<S2<⋯<SM=N1=S_1<S_2<\cdots<S_M=N$ 。

输入

输出

提示

来源

[提交][状态]