c**i
发帖数: 306 | 1 You are driving a bus along a highway, full of rowdy, hyper, thirsty
students and a soda fountain
machine. Each minute that a student is on your bus, that student drinks one
ounce of soda. Your
goal is to drop the students off quickly, so that the total amount of soda
consumed by all students
is as small as possible.
You know how many students will get off of the bus at each exit. Your bus
begins somewhere
along the highway (probably not at either end) and move s at a constant
speed of 37.4 miles per
hour. You must drive the bus along the highway; however, you may drive
forward to one exit then
backward to an exit in the opposite direction, switching as often as you
like. (You can stop the
bus, drop off students, and turn around instantaneously.)
Describe an efficient algorithm to drop the students off so that they drink
as little soda as
possible. Your input consists of the bus route (a list of the exits,
together with the travel time
between successive exits), the number of students you will drop off at each
exit, and the current
location of your bus (which you may assume is an exit).
求大牛们share个思路，thanks | e********2
发帖数: 495 | 2 作业题吧？哥给你个提示，2D-DP，类似于edit distance。
one
【在 c**i 的大作中提到】
: You are driving a bus along a highway, full of rowdy, hyper, thirsty
: students and a soda fountain
: machine. Each minute that a student is on your bus, that student drinks one
: ounce of soda. Your
: goal is to drop the students off quickly, so that the total amount of soda
: consumed by all students
: is as small as possible.
: You know how many students will get off of the bus at each exit. Your bus
: begins somewhere
: along the highway (probably not at either end) and move s at a constant
| c**i
发帖数: 306 | 3
不是作业，一个面试题：http://www.careercup.com/question?id=5690555409367040
可否细说下DP记录的是什么信息？还是有点晕
【在 e********2 的大作中提到】
: 作业题吧？哥给你个提示，2D-DP，类似于edit distance。
:
: one
|
|
