11. 贪心与动态规划（二）.pdf

: .
ACM算法y 所在位
置下方第一块板左端为起点到地面的最短时间，和右端为起点
到地面的最短时间。这两个子问题在形式上和原问题是完全一
致的。
将板子从上到下从1 开始进行无重复的编号(高度相同的板
子，哪块编号在前无所谓)，那么，和上面两个子问题相关的
变量就只有板子的编号。
6/34所以，本题目的2、解题思路“状态”就是板子编号，而一个“状态”对应的
“值”有两部分，是两个子问题的解，即从该板子左端出发到达
地面的最短时间，和从该板子右端出发到达地面的最短时间。
不妨认为Jimmy 开始的位置是一个编号为0，长度为0 的板
子，假设LeftMinTime(k)表示从k 号板子左端到地面的最短
时间，RightMinTime(k)表示从k 号板子右端到地面的最短
时间，那么，求板子k 左端点到地面的最短时间的方法如下：
if ( 板子k 左端正下方没有别的板子) 
{
if( 板子k 的高度 h(k) 大于Max)
LeftMinTime(k) =  ∞;
else
LeftMinTime(k) = h(k);
}
else if( 板子k 左端正下方的板子编号是m )
LeftMinTime(k) = h(k)‐h(m) + 
Min(LeftMinTime(m)+Lx(k)‐Lx(m),
RightMinTime(m)+Rx(m)‐Lx(k));  
7/342、解题思路
上面，h(i)就代表i 号板子的高度，Lx(i)就代表i 号板
子左端点的横坐标，Rx(i)就代表i号板子右端点的横坐标。
那么 h(k)‐h(m) 当然就是从k 号板子跳到m 号板子所需要
的时间，Lx(k) ‐Lx(m) 就是从m 号板子的落脚点走到m 号板
子左端点的时间，Rx(m)‐Lx(k)就是从m号板子的落脚点走到
右端点所需的时间。
求RightMinTime(k)的过程类似。
不妨认为Jimmy 开始的位置是一个编号为0，长度为0 的板
子，那么整个问题就是要求LeftMinTime(0)。
输入数据中，板子并没有按高度排序，所以程序中一定要首
先将板子排序。
8/34#include、参考程序 <>
#include3  <>
#include <>
#define MAX_N 1000
#define INFINITE 1000000
int t, n, x, y, max;
struct Platform
{
int Lx, Rx, h;
} ;
Platform aP