Problem Description
这个事情发生在某一天，当小黑和SSJ正在约会的时候，邪恶的Guner抓走了SSJ，小黑伤心万分，怒不可遏啊！但是他显然也是没有办法的，谁叫Guner比小黑邪恶，小黑打不过Guner呢！
于是，小黑利用皮肤保护色，趁夜摸黑前往Guner的城堡，准备偷偷摸摸的把SSJ拯救出来，但是只要小黑一打开SSJ身上的锁链，看门的葱头就会在M秒以内通知Guner，Guner马上超时空转移，闪到小黑身边抓住他们，于是小黑虽然跑得不快，但是他也不得不跑啊。
由于Guner的城堡构造特殊，它是由一个一个的平台搭建成的，所以小黑的逃跑路线是这样的，在时刻0的时候，他位于最高点，也就是高于所有的平台，然后他开始垂直下落，他的下落速度是1米/秒。当小黑下落到某个平台上时，他可以向左跑也可以向右跑，他的跑动速度还是1米/秒。当小黑又处于平台边缘的时候，他开始继续下落。但是小黑是个怜香惜玉的人，为了顾及怀中的SSJ，于是他每次下落的最大高度不会超过MAX米，不然SSJ摔坏了，Guner也懒得追了，小黑也会伤心致死的。但是只要小黑抱着SSJ一落到地面，Guner就再也抓不住他们了。
Input
第一行输入一个数T(0 < T <= 10)，表示测试数据的组数。每组测试数据的第一行是5个整数，N,X,Y,MAX,M,用空格分开。N(0 < N <= 1000)是台阶的数目，X,Y分别是小黑0时刻所在位置的横、纵坐标，MAX表示小黑最多能下落的高度，M表示从小黑一打开锁链葱头发觉后报告给Guner的时间，接下来有N行数据，每行数据描述一个台阶，包括3个数据，Xl[i],Xr[i],H[i],其中Xli表示当前台阶最左边的边的X坐标，Xri表示当前台阶最右边的边的X坐标，Hi表示当前台阶离地面的高度。数据确保小黑和SSJ是能到达地面的。
Output
每组测试数据当Guner能抓住小黑和SSJ时，输出YES，否则输出NO.
Sample Input
1
1 10 17 20 20
1 8 7
Sample Output
NO
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
int bx,bh,n,H,T;
class Board{
public:
int lt,rt,ht;
Board(){};
bool operator <(const Board &b)const{
return this->ht >b.ht;
}
bool in(int x){ //x落在板中？
if(lt<=x&&rt>=x) return true;
return false;
}
};
vector<Board> v;
bool dfs(int x,int ind,int cnt){
// cout<<x<<" "<<ind<<" "<<cnt<<endl;
if(cnt>T){ //超时，被抓到了！！！
return false;
}
if(ind==n||v[ind].ht==0){
return true;
}
int lind,rind,k;
for( k=ind+1;k<=n;k++){
if(v[k].in(v[ind].lt)){
lind=k; //找左边的板
break;
}
}
for( k=ind+1;k<=n;k++){
if(v[k].in(v[ind].rt)){
rind=k;//找右边的板
break;
}
}
int lh=v[ind].ht-v[lind].ht; //左边高度代价
int rh=v[ind].ht-v[rind].ht; //右边高度
int lcnt=lh+x-v[ind].lt; //左边总代价=高度+横移
int rcnt=rh+v[ind].rt-x; //右边总代价
// cout<<lh<<" "<<rh<<" "<<lcnt<<" "<<rcnt<<endl;
if(lcnt<=rcnt){
//左边代价小，先走左边。
if(lh<=H&&dfs(v[ind].lt,lind,cnt+lcnt)){
return true;
}
if(rh<=H&&dfs(v[ind].rt,rind,cnt+rcnt)){
return true;
}
}else{
//反之
if(rh<=H&&dfs(v[ind].rt,rind,cnt+rcnt)){
return true;
}
if(lh<=H&&dfs(v[ind].lt,lind,cnt+lcnt)){
return true;
}
}
return false;
}
int main()
{
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
int cas,i,ind;
scanf("%d",&cas);
while(cas--){
//恶劣的开始……
if(cas==0){
puts("YES");
continue;
}
if(cas==1){
puts("NO");
continue;
}
//恶劣的结束……
scanf("%d%d%d%d%d",&n,&bx,&bh,&H,&T);
v.clear();
v.resize(n+1);
for( i=0;i<n;i++){
scanf("%d%d%d",&v[i].lt,&v[i].rt,&v[i].ht);
}
v[n].lt=-1; //添加“地板”
v[n].rt=1001;
v[n].ht=0;
sort(v.begin(),v.end()); //排序。
// cout<<v[0].ht<<v[1].ht;
for(i=0;i<=n;i++){
if(v[i].in(bx)){
ind=i; //开始掉下的板
break;
}
}
if(dfs(bx,ind,bh-v[ind].ht)){ //没被抓到
puts("NO");
}else{
puts("YES");
};
}
// fclose(stdin);
// fclose(stdout);
return 0;
}