湖南省省赛题目湖南省省赛题目.docVIP

The 11th Hunan Collegiate Programming Contest Online Version (with more input data and tighter time limits) 30th August, 2015 You get 13 Pages 11 Problems 300 Minutes A Aerial Tramway Input: Standard Input Output: Standard Output ? 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,yi0, xixi+1, yi!=yi+1 (that means there will not be horizontal segments in the mountain skyline), illustrated below (the x-coordinate of pi is i): 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. ykyi for every ikj. For example, no tram can travel between p2 and p9, because p4 is not strictly below p2-p9. However, you can have two trams, one from p2 to p4, and one p4 to p9. There is another important restriction: no point can be strictly below k or more tramways, because it’ll be dangerous. For example, if k=3, we cannot build these 3 tramways simultaneously: p1-p14, p4-p9, p6-p8, because p7 would be dangerous. 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