3006: Long Distance Racing 越野跑
题目描述
Bessie is training for her next race by running on a path that includes hills so that she will be prepared for any terrain. She has planned a straight path and wants to run as far as she can -- but she must be back to the farm within M seconds (1 ≤ M ≤ 10,000,000).
The entire path she has chosen is T units (1 ≤ T ≤ 100,000) in length and consists of equal-length portions that are uphill, flat, or downhill. The input data describes path segment i with a single character Si that is u, f, or d, indicating respectively uphill, flat, or downhill.
Bessie takes U seconds (1 ≤ U ≤ 100) to run one unit of uphill path, F (1 ≤ F ≤ 100) seconds for a unit of flat path, and D (1 ≤ D ≤ 100) seconds for a unit of downhill path. Note that, when returning home, uphill paths become downhill paths and downhill paths become uphill paths.
Find the farthest distance Bessie can get from the farm and still make it back in time.
输入
* Line 1: Five space-separated integers: M, T, U, F, and D
* Lines 2..T+1: Line i+1 describes path segment i with a single letter: Si
输出
* Line 1: A single integer that is the farthest distance (number of units) that Bessie can get from the farm and make it back in time.
样例输入 复制
13 5 3 2 1
u
f
u
d
f样例输出 复制
3提示
输入说明:
贝茜跑步的最大耗时为13秒（这么短...），她跑步的山路一共被划成5段。贝茜跑完一段上坡路的耗时为3秒，平地为2秒，下坡路为1秒。山路各段的走向如下图所示：
_/\_ /
输出说明:
贝茜跑完山路的前3段，然后返回，总耗时为3 + 2 + 3 + 1 + 2 + 1 = 12 秒，只比她能在外面呆的时限少1秒。如果她跑得更远，就无法按时回到农场。