1661.cpp

poj题目

#include<iostream>
using namespace std;
int maxt,n,x,y;
struct a
{
	int x1;
	int x2;
	int h;
}platform[1100];
int statusleft[2000];
int statusright[2000];
int compare(const void*c,const void *d)
{
	return -(((a*)c)->h-((a*)d)->h);
}
int jump(int from,int x)
{
	int i;
	int mint=0;
	int timer=0;
	int timel=0;
	int left=0,right=0;
	if(from==n)
		return 0;
	for(i=from+1;i<=n;i++)
	{
		if(platform[from].h-platform[i].h>maxt)
		    break;
		if(platform[i].x2>=platform[from].x2&&platform[i].x1<=platform[from].x2)//right
		{
			right=i;
			break;
		}
	}
	if(right!=0)
	{
		if(statusright[from]==0)
	    {
			statusright[from]=jump(right,platform[from].x2)+platform[from].h-platform[right].h;

		}
			timer=statusright[from]+platform[from].x2-x;
	}
	else
	{
		timer=99999999;
		statusright[from]=99999999;
	}
	for(i=from+1;i<=n;i++)
	{
		if(platform[from].h-platform[i].h>maxt)
		    break;
		if(platform[i].x1<=platform[from].x1&&platform[i].x2>=platform[from].x1)//left
		{
			left=i;
			break;
		}
	}
         if(left!=0)
		 {
			 if(statusleft[from]==0)
			 {
				 statusleft[from]=jump(left,platform[from].x1)+platform[from].h-platform[left].h;
			 }
			timel=statusleft[from]+x-platform[from].x1;
		}
	    else
		{
			timel=99999999;
			statusleft[from]=99999999;
		}
        if(timer>timel)
			mint=timel;
		else
		{
			mint=timer;
		}
		return mint;
}
int main()
{
	int t,i,time,start;
	cin>>t;
	while(t--)
	{
		memset(platform,0,sizeof(platform));
		memset(statusright,0,sizeof(statusright));
		memset(statusleft,0,sizeof(statusleft));
		cin>>n>>x>>y>>maxt;
		for(i=0;i<n;i++)
			cin>>platform[i].x1>>platform[i].x2>>platform[i].h;
	   qsort((void*)platform,n+1,sizeof(platform[0]),compare);
		platform[n].h=0;
		platform[n].x1=-21000;
		platform[n].x2=21000;
		for(i=0;i<=n;i++)
		{
			if(x<=platform[i].x2&&x>=platform[i].x1)
			{
				start=i;
				break;
			}
		}
		time=jump(start,x)+y-platform[start].h;
		cout<<time<<endl;
	}
}