> #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!!!动规哪里出错了啊？ (36) seachingdream 2006-04-16 16:53:39