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

不知道算什么。。。压缩路径做的。。。。5XXms......

Posted by lvhao945 at 2010-08-15 07:05:10 on Problem 2452
#include <iostream>
using namespace std;
int p[50005],q[50005];
int main()
{
	int n,i,j;
	while(scanf("%d",&n)!=EOF)
	{
		for(i=1;i<=n;i++)
		{
			scanf("%d",&p[i]);
			q[i]=1;
		}
		p[n+1]=-1;
		for(i=n;i>0;i--)
		{
			while(p[i]<p[i+q[i]])
				q[i]+=q[i+q[i]];
		}
		int ans=0;
		for(i=1;i<=n;)
		{
			int max=-1,tag=-1;
			for(j=0;j<q[i];j++)
			{
				if(p[i+j]>max)
				{
					max=p[i+j];
					tag=j;
				}
			}
			if(tag>ans)ans=tag;
			i+=tag+1;
		}
		if(ans==0)puts("-1");
		else printf("%d\n",ans);
	}
	return 0;
}

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