一道题（转化为图）

原文：

      You are going on a long trip. You start on the road at mile post 0. Along the way there are n hotels, at mile posts a1 < a2 < · · · < an , where each ai is measured from the starting point. The only places you are allowed to stop are at these hotels, but you can choose which of the hotels you stop at. You must stop at the final hotel (at distance an ), which is your destination.
    You’d ideally like to travel 200 miles a day, but this may not be possible (depending on the spacing of the hotels). If you travel x miles during a day, the penalty for that day is (200 − x)^2 . You want to plan your trip so as to minimize the total penalty—that is, the sum, over all travel days, of the daily penalties.
大意：

      你将要进行一次长途旅行。旅行起点标记为0英里。沿途有n个hotel，它们的位置分别是a1 < a2 <……< an，ai是从出发点测量的结果。只能停在hotel里，但可以选择停在哪个hotel。目标是停在an。
      理想的情况是每天行进200英里，但这也许是不可能的（取决于hotel之间的距离）。如果每天行进x英里，penalty是(200-x)的平方。你为旅行做计划，使得总penalty最小。

      ai既代表第i个hotel，又代表第i个hotel到起点的距离。

解法：

我们把hotel a1…an放在一条直线上，从左到右依次排列。任意一对hotel(ai, aj), i<j，有一条弧。这条弧表示：某一天，从ai行进到了aj。这条弧的代价是(200-(aj-ai))的平方。这样，我们得到一个有向无环图。问题转化求这个有向无环图中节点a1到节点an的最短路径。