Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
欢迎参加IJCAI 2020麻将智能体竞赛,大奖等你拿!Welcome to IJCAI 2020 Mahjong AI competition with amazing prizes! | 北京大学《ACM/ICPC大学生程序设计竞赛训练》暑期课面向全球招生!

讨论区唯一一组wa的数组太长了,看不了,,顺便整理了一下测试数据留在这里以后再来改吧

Posted by 918106840125 at 2019-07-28 19:56:29 on Problem 1661
#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 
*/











Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator