Rest Stops

题目描述

农夫 John 和他的私人教练 Bessie 正在攀登 Vancowver 山。为方便起见（对你也是），这座山可以表示为一条长度为 $L$ 米的笔直步道（$1 \leq L \leq 10^6$）。农夫 John 将以恒定的行进速度在步道上行走，每米需要 $r_F$ 秒（$1 \leq r_F \leq 10^6$）。由于他在训练耐力，他一路上不会进行任何休息。

然而，Bessie 允许进行休息，在休息点她可能找到一些美味的草。当然，她不能在任意位置停下！步道上有 $N$ 个休息点（$1 \leq N \leq 10^5$）；第 $i$ 个休息点距离步道起点 $x_i$ 米（$0 < x_i < L$），其美味值为 $c_i$（$1 \leq c_i \leq 10^6$）。如果 Bessie 在休息点 $i$ 休息 $t$ 秒，她将获得 $c_i \cdot t$ 的美味单位。

不在休息点时，Bessie 将以固定行进速度行走，每米需要 $r_B$ 秒（$1 \leq r_B \leq 10^6$）。由于 Bessie 年轻且健壮，$r_B$ 严格小于 $r_F$。

Bessie 希望最大化自己吃到的美味草总量。但她担心农夫 John；她认为如果在徒步过程中的任何时刻她在步道上落后于农夫 John，他可能会失去继续前进的所有动力！

请帮助 Bessie 在确保农夫 John 能完成徒步的前提下，求出她能获得的最大总美味单位数。

输入格式

输入格式（文件 reststops.in）： 输入第一行包含四个整数：$L$、$N$、$r_F$、$r_B$。 接下来 $N$ 行描述各个休息点。对于每个 $1$ 到 $N$ 的 $i$，第 $i+1$ 行包含两个整数 $x_i$ 和 $c_i$，分别表示第 $i$ 个休息点的位置以及该处草的美味值。 保证 $r_F > r_B$，且 $0 < x_1 < \dots < x_N < L$。 注意 $r_F$ 和 $r_B$ 的单位是“每米所需秒数”！

输出格式

输出格式（文件 reststops.out）： 输出一行一个整数：Bessie 能获得的最大总美味单位数。

10 2 4 3
7 2
8 1

15

提示

在这个例子中，Bessie 的最优策略是在 $x=7$ 的休息点停留 $7$ 秒（获得 $14$ 美味单位），然后在 $x=8$ 的休息点再额外停留 $1$ 秒（再获得 $1$ 美味单位，总计 $15$ 美味单位）。 题目致谢：Dhruv Rohatgi

标签: USACO|2018|Silver

来源

USACO|2018|Silver