题目链接：http://poj.org/problem?id=1661
下图是左边的，右边的同理：
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;
#define N 1100
#define INF 0xffffff
struct node
{
int L, R, H;
} a[N];
int cmp(node p, node q)
{
return p.H > q.H;
}
int main()
{
int T, n, x, y, m,dp[N][];
scanf("%d", &T);
while(T--)
{
scanf("%d %d %d %d", &n, &x, &y, &m);
for(int i=; i<=n; i++)
{
scanf("%d %d %d", &a[i].L, &a[i].R, &a[i].H);
dp[i][] = dp[i][] = INF;
}
int ans=INF;
a[].L = x;
a[].R = x;
a[].H = y;
sort(a, a+n+, cmp);///按高度排序； a[n+].L = -;
a[n+].R = ;
a[n+].H = ;///地面； dp[][] = dp[][] = ;
for(int i=; i<=n; i++)
{
int LL=, RR=;///LL和RR用于标记从第i块木板左右两端下落是否找到了下一个落脚点
for(int j=i+; j<=n+; j++)
{
if( (!LL&&!RR) || (a[i].H-a[j].H>m) )///当不满足高度或者已经有下一落点时就可以跳出来了；
break;
if(a[i].L>=a[j].L && a[i].L<=a[j].R && a[i].H!=a[j].H && LL)///当i从左边下落到下一平台j时；
{
LL=;///已经在左边找到落点；
if(j==n+)///如果落点为地面就可以取最小值了；
ans=min(ans, dp[i][]);
else///否侧就。。。画个图，一眼就看明白了；
{
dp[j][]=min(dp[j][], dp[i][]+(a[i].L-a[j].L));
dp[j][]=min(dp[j][], dp[i][]+(a[j].R-a[i].L));
}
}
if(a[i].R>=a[j].L && a[j].R>=a[i].R && a[i].H!=a[j].H && RR)///和上面同理；
{
RR=;
if(j==n+)
ans=min(ans, dp[i][]);
else
{
dp[j][]=min(dp[j][], dp[i][]+(a[i].R-a[j].L));
dp[j][]=min(dp[j][], dp[i][]+(a[j].R-a[i].R));
}
}
}
}
printf("%d\n", ans+y);
}
return ;
}