#include <iostream.h>
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
int N,X,Y,max;
int feet;
struct board 
{
	int x1,x2,height;
	int left;
	int right;
};
int mycompare(const void *p1,const void *p2)
{
	board *pp1=(board*)p1;
	board *pp2=(board*)p2;
	if (pp1->height == pp2->height )
		return (pp1->x1-pp2->x1);
	return (pp1->height-pp2->height);
}
int min(int a,int b)
{
	if (a<b)
		return a;
	else return b;
}
board list[1001];
int result [1001][2];//建立动规数组
void main()
{
	int n;
	scanf("%d",&n);
	while (n--)
	{
		scanf("%d%d%d%d",&N,&X,&Y,&max);
		for (int i=0;i<N;i++)
		{
			scanf ("%d%d%d",&(list[i].x1),&(list[i].x2),&(list[i].height));
			
		}
		qsort(list,N,sizeof (board),mycompare);
		result [0][0]=0;result[0][1]=0;
		for (int j=1;j<N;j++)
		{
			if (list[j].height==list[0].height)
			{
				result[j][0]=0;
				result[j][1]=0;

			}
			else 
			{
				result[j][0]=pow(2,30);
				result[j][1]=pow(2,30);
			}
		}
		for (int c=1;list[c].height==list[0].height;c++);
		
		for (int k=c;k<N;k++)
		{
			int a,b;
			for ( a=k-1;a>=0;a--)//依次给每个板左右两端赋值
			{
				if (list [k].height-list[a].height<=max&&list[k].x1>=list[a].x1
					&&list[k].x1<=list[k].x2)
				{
					result[k][0]=min(result[a][0]+list[k].x1-list[a].x1,
										result[a][1]+list[a].x2-list[k].x1);
					break;
				}
			}
			
			if (a==-1&&list[k].height<=max)
				result[k][0]=0;
			for ( b=k-1;b>=0;b--)
			{
				if (list [k].height-list[b].height<=max&&list[k].x2>=list[b].x1
					&&list[k].x2<=list[b].x2)
				{
					result[k][1]=min(result[b][0]+list[k].x2-list[b].x1,
										result[b][1]+list[b].x2-list[k].x2);
					break;
				}
			}
			if (b==-1&&list[k].height<=max)
				result[k][1]=0;
		}
		for (int d=N-1;d>=0;d--)
		{
			if (list[d].x1<=X&&list[d].x2>=X)
			{
				feet=Y+min(result[d][0]+X-list[d].x1,result[d][1]+list[d].x2-X);
				break;
			}
		}
		if (d==-1)
			feet=Y;
		printf("%d\n",feet);
	}
}
			
		

		
		

• Re:WA!!help!!!动规哪里出错了啊？ (2232) seachingdream 2006-04-16 16:52:58
  • Re:WA!!help!!!动规哪里出错了啊？ (36) seachingdream 2006-04-16 16:53:39