| 题目名称 | 3033. [USACO Feb18 Silver]Rest Stops |
|---|---|
| 输入输出 | reststops_silver_18feb.in/out |
| 难度等级 | ★★☆ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 10 |
| 题目来源 |
 yuan
于2018-10-31加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：14， 提交：27， 通过率：51.85% | ||||
 梦那边的美好ET |
100 | 0.128 s | 1.84 MiB | C++ |
 leon |
100 | 0.143 s | 1.29 MiB | C++ |
|
leon |
100 | 0.196 s | 1.84 MiB | C++ |
|
aaaa1218 |
100 | 0.247 s | 11.00 MiB | C++ |
 APWTMECRD |
100 | 0.249 s | 1.83 MiB | C++ |
 烟雨 |
100 | 0.250 s | 1.83 MiB | C++ |
|
┭┮﹏┭┮ |
100 | 0.292 s | 0.00 MiB | C++ |
|
夜莺 |
100 | 0.384 s | 5.92 MiB | C++ |
 瑆の時間~無盡輪迴·林蔭 |
100 | 0.506 s | 1.08 MiB | C++ |
|
yuan |
100 | 0.533 s | 1.17 MiB | C++ |
| 关于 Rest Stops 的近10条评论(全部评论) |
|---|
3033. [USACO Feb18 Silver]Rest Stops
★★☆ 输入文件：reststops_silver_18feb.in
输出文件：reststops_silver_18feb.out
简单对比时间限制：1 s 内存限制：256 MiB
【题目描述】
Farmer John和他的私人教练Bessie正在徒步攀登温哥牛山。基于他们的目的（也是你的目的），这座山可以用一条长为L米（1≤L≤10^6）的长直路径表示。Farmer John会沿着这条路径以每米rF秒（1≤rF≤10^6）的固定速度攀登。由于他正在训练他的耐力，他在途中不会进行任何的休息。
然而Bessie可以在休息站休息，在那里她能够找到一些美味的嫩草。当然，她也不能在任何地方都休息！在路径上总共有N个休息站（1≤N≤10^5）；第i个休息站距离路径的起点xi米（0<xi<L），美味值为ci（1≤ci≤10^6）。如果Bessie在休息站i休息了t秒，她能够得到ci*t个美味单位。
不在休息站的时候，Bessie会以每米rB秒（1≤rB≤10^6）的固定速度攀登。由于Bessie年轻而健康，rB严格小于rF。
Bessie想要吃到最多的美味嫩草。然而她也担心Farmer John；她认为如果在任何时候她位于Farmer John身后，Farmer John可能就会失去前进的动力了！
帮助Bessie求出，在确保Farmer John能够完成登山的情况下，她能够获得的最多的美味单位。
【输入格式】
输入的第一行包含四个整数：L，N，rF，以及rB。下面N行描述了休息站。对于1至N之间的每一个i，第i+1行包含了两个整数xi和ci，描述了第i个休息站的位置和那里的草的美味值。
输入保证rF>rB，并且0<x1<⋯<xN<L。注意rF和rB的单位为秒每米！
【输出格式】
输出一个整数：Bessie可以获得的最多的美味单位。
【样例输入】
10 2 4 3 7 2 8 1
【样例输出】
15
【提示】
在这个样例中，Bessie的最佳方案是在位于x=7的休息站停留7秒（获得14个美味单位），再在位于x=8的休息站停留1秒（再获得1个美味单位，总共是15个美味单位）。
【来源】
USACO 2018 February Contest SILVER Problem 1
供题：Dhruv Rohatgi