An aerial tramway, cable car, ropeway or aerial tram is a type of aerial lift which uses one or two stationary ropes for support while a third moving rope provides propulsion. With this form of lift, the grip of an aerial tramway cabin is fixed onto the propulsion rope and cannot be decoupled from it during operations.
-- Wikipedia
You own a park located on a mountain, which can be described as a sequence of n points (xi, yi) from
left to right, where xi,yi>0, xi
Since the mountain is very sloppy, some aerial tramways across the park would be very helpful. In the figure above, people can go from p4 to p9 directly, by taking a tram. Otherwise he must follow a rather zigzag path: p4-p5-p6-p7-p8-p9.
Your job is to design an aerial tramway system. There should be exactly m trams, each following a
horizontal segment in the air, between two points pi and pj. "Horizontal" means yi=yj, “in the air"
means all the points in between are strictly below, i.e. yk
You want to make this system as useful as possible, so you would like to maximize the total length of all tramways. For example, if m=3, k=3, the best design for the figure above is p1-p14, p2-p4 and p4-p9, the total length is 20. If m=3, k=2, you have to replace p1-p14 with p11-p13, the total length becomes 9.
14 3 3 1 8 2 6 3 4 4 6 5 3 6 4 7 1 8 4 9 6 10 4 11 6 12 5 13 6 14 8 14 3 2 1 8 2 6 3 4 4 6 5 3 6 4 7 1 8 4 9 6 10 4 11 6 12 5 13 6 14 8
Case 1: 20 Case 2: 9
无
第十一届“蓝狐网络杯”湖南省大学生计算机程序设计竞赛