蛮麻烦的一个题 但是说白了 也就是一个类似最长上升子序列的东西（可能跳转的跨度大了些） 从底部往上逐层DP,每一层有两个状态 分别求之。小结一下吧 做了这么多动态规划题 我发现 动态规划的实质 居然是穷举 ，囧啊，或者更确切的来说是 带记忆化的穷举！存储加递归应该还是欠妥的，因为毕竟有了最优子结构以后 后效状态便消除了，而且也并没有揭示出DP解法的全局性（如果用更宏观的视角来看待它），即它在求得答案的同时，也获得了其他更多的信息，这些信息不是冗余（redundant 恩GRE高频词），形象的说 应该是在DP之路上，为答案作出贡献的朋友，如果我们换一个问题，也许它们也就成了答案。
对了，补充一下，我觉得这个题最重要的地方在于，当你找到了一块板刚好能接住从左侧下降的你时，你便不用再考虑更下层的板了，因为你不可能穿墙（板）！
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
#define INF 999999999
struct node
{
int x1;
int x2;
int h;
bool operator <(node other)
{
return h>other.h;
}
}a[1005];
int dp[1001][2];
int n,x,y,mh;
int main()
{
int t;
int i,j,k;
scanf("%d",&t);
for(k=1;k<=t;k++)
{
scanf("%d%d%d%d",&n,&x,&y,&mh);
for(i=1;i<=n;i++)
{
scanf("%d%d%d",&a[i].x1,&a[i].x2,&a[i].h);
dp[i][0]=dp[i][1]=INF;
}
dp[n+1][0]=dp[n+1][1]=0;
a[n+1].x1=-INF;
a[n+1].x2=INF;
sort(a+1,a+1+n);
for(i=n;i>=1;i--)
{
bool l=false;
bool r=false;
for(j=i+1;j<=n+1;j++)
{
if(a[i].h-a[j].h>mh)
break;
if(!l&&a[i].x1>=a[j].x1&&a[i].x1<=a[j].x2)
{
if(j==n+1) dp[i][0]=0;
else
{
dp[i][0]=min(dp[i][0],dp[j][0]+a[i].x1-a[j].x1);
dp[i][0]=min(dp[i][0],dp[j][1]+a[j].x2-a[i].x1);
l=true;
}
}
if(!r&&a[i].x2>=a[j].x1&&a[i].x2<=a[j].x2)
{
if(j==n+1) dp[i][1]=0;
else
{
dp[i][1]=min(dp[i][1],dp[j][0]+a[i].x2-a[j].x1);
dp[i][1]=min(dp[i][1],dp[j][1]+a[j].x2-a[i].x2);
r=true;
}
}
}
}
int res=0;
for(i=1;i<=n+1;i++)
{
if(a[i].x1<=x&&x<=a[i].x2&&y>=a[i].h)
{
res=min(x-a[i].x1+dp[i][0],a[i].x2-x+dp[i][1]);
break;
}
}
res+=y;
printf("%d\n",res);
}
return 0;
}