> #include<iostream>
> #include<cstdio>
> #include<algorithm>
> #include<cstring>
> #include<map>
> using namespace std;
> const int maxn=1000+5;
> const int inf=0x3f3f3f3f;
> map<pair<int,int>,bool>vis;
> struct Block{
> 	int lx,rx,h;
> }block[maxn];
> int minleft[maxn],minright[maxn];//minleft[i]表示第i块平台左端掉到地面最少时间,minright同理
> int n,x,y,MAX,t,pos;
> bool cmp(Block b1,Block b2)
> {
> 	return b1.h>b2.h;
> }
> int dfs(int k,int p)
> {
> 	if(vis[make_pair(k,p)]==1)return min(minleft[k],minright[k]);
> 	if(k==n)
> 	{
> 		int lx=abs(pos-block[n].lx);
> 		int rx=abs(pos-block[n].rx);
> 		if(block[n].h>MAX) minleft[n]=minright[n]=2*inf;	
> 		else {
> 			minleft[n]=block[n].h+lx;
> 			minright[n]=block[n].h+rx;
> 		}
> 		return min(minleft[n],minright[n]); 
> 	}
> 	int lx=abs(pos-block[k].lx);
> 	int rx=abs(pos-block[k].rx);
> 	int tmpl=-1,tmpr=-1;
> 	for(int i=k+1;i<=n;i++)
> 	{
> 		if(block[i].lx<=block[k].lx&&block[i].rx>=block[k].lx)
> 		{
> 			tmpl=i;break;
> 		}
> 	}
> 	for(int i=k+1;i<=n;i++)
> 	{
> 		if(block[i].lx<=block[k].rx&&block[i].rx>=block[k].rx)
> 		{
> 			tmpr=i;break;
> 		}
> 	}
> 	if((tmpl==-1&&block[k].h>MAX)||(tmpl!=-1&&abs(block[k].h-block[tmpl].h)>MAX))
> 	minleft[k]=2*inf;
> 	else 
> 	{
> 		if(tmpl==-1)minleft[k]=block[k].h+lx;
> 		else
> 		{
> 			pos=block[k].lx;
> 			minleft[k]=dfs(tmpl,pos)+lx+abs(block[k].h-block[tmpl].h);
> 			vis[make_pair(tmpl,block[k].lx)]=1;	
> 		}
> 	}
> 	if((tmpr==-1&&block[k].h>MAX)||(tmpr!=-1&&abs(block[k].h-block[tmpr].h)>MAX))
> 	minright[k]=2*inf;
> 	else 
> 	{
> 		if(tmpr==-1)minleft[k]=block[k].h+rx;
> 		else{
> 			pos=block[k].rx;
> 			minright[k]=dfs(tmpr,pos)+rx+abs(block[k].h-block[tmpr].h);
> 			vis[make_pair(tmpr,block[k].rx)]=1;
> 		}
> 	}	
> 	return min(minleft[k],minright[k]);
> }
> int main()
> {
> 	scanf("%d",&t);
> 	while(t--)
> 	{
> 		memset(block,0,sizeof(block));
> 		scanf("%d%d%d%d",&n,&x,&y,&MAX);
> 		for(int i=1;i<=n;i++) 
> 		scanf("%d%d%d",&block[i].lx,&block[i].rx,&block[i].h);
> 		block[0]={x,x,y};
> 		sort(block+1,block+1+n,cmp);
> 		memset(minleft,0x3f,sizeof(minleft));
> 		memset(minright,0x3f,sizeof(minright));
> 		pos=x;
> 		vis.erase(vis.begin(),vis.end());
> 		printf("%d\n",dfs(0,x));
> 	}
> 	return 0;
> }
> /*
> 1
> 4 14 5 6
> 3 22 1
> 16 23 2
> 16 30 3
> 13 21 4
> 答案:15
> 1
> 2 2 12 8
> 0 10 10
> 2 12 5
> 答案:22
> 2
> 3 8 7 2
> 6 14 6
> 4 10 4
> 5 14 2
> 1 6 10 20
> 2 3 5
> answer:
> 17 10
> 
> 1
> 3 8 12 8
> 0 10 4
> 0 10 10
> -2 4 6
> 
> 1
> 10 899 52 50
> 893 903 18
> 890 900 38
> 898 908 8
> 910 920 8
> 894 904 43
> 881 891 18
> 872 882 38
> 867 877 43
> 842 852 43
> 895 905 3
> Ans：
> 61
> 
> 4
> 3 4 4 5
> 3 5 3
> 1 7 2
> 2 6 1
> 3 8 17 20
> 0 10 8
> 0 10 13
> 4 14 3
> 3 4 4 5
> 3 5 3
> 1 4 2
> 2 6 1
> 3 4 4 5
> 3 6 3
> 5 7 2
> 1 4 1
> 答案:14 
> 1
> 3 8 17 20
> 8 10 8
> 8 10 13
> 8 14 3
> ans:17
> 以上数据都过了,wa到怀疑人生.... 
> 这组数据我输出353了,不过是无效数据,太难查了...
> 1
> 60 822 302 50
> 813 823 298
> 813 823 293
> 816 826 213
> 816 826 178
> 817 827 218
> 813 823 148
> 821 831 73
> 814 824 248
> 813 823 283
> 815 825 158
> 819 829 58
> 814 824 13
> 813 823 28
> 819 829 233
> 814 824 43
> 773 783 293
> 821 831 93
> 818 828 268
> 816 826 198
> 818 828 113
> 814 824 208
> 816 826 68
> 821 831 133
> 794 804 248
> 814 824 108
> 829 839 28
> 818 828 143
> 844 854 298
> 802 812 133
> 801 811 28
> 818 828 238
> 817 827 8
> 816 826 48
> 820 830 3
> 819 829 288
> 822 832 138
> 820 830 183
> 855 865 13
> 777 787 268
> 820 830 63
> 789 799 28
> 822 832 33
> 855 865 213
> 779 789 208
> 836 846 248
> 806 816 33
> 821 831 263
> 818 828 83
> 846 856 263
> 789 799 68
> 854 864 8
> 854 864 283
> 801 811 298
> 805 815 143
> 822 832 23
> 821 831 173
> 813 823 153
> 858 868 138
> 818 828 98
> 839 849 133
> 答案:352 
> */
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 

• Re:讨论区唯一一组wa的数组太长了,看不了,,顺便整理了一下测试数据留在这里以后再来改吧 (41) 977955490 2020-04-04 08:49:06