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

why wa?

Posted by ftstar at 2007-04-12 15:21:43 on Problem 3214
#include<cstdio>
#include<cmath>
#include<algorithm>

const	int		maxn=1048576;


int		n,t,ans,x;
int		a[maxn];
int		q[maxn];
int		res[maxn];


void	dfs(int	v)
{	
	int		temp;
	if (v*2<=t)dfs(v*2);
	if (v*2+1<=t)x++;
	temp=x;
	if (v*2+1<=t)dfs(v*2+1);
	q[0]++;
	q[q[0]]=a[v]-temp;
}

void	init()
{
	int		i,j;
	
	memset(q,0,sizeof(q));
	ans=0;	
	
	scanf("%d\n",&n);
	
	t=0;
	for (i=0;i<n;i++)
	{	
		for (j=1;j<=pow(2,i);j++)
		{			
			if (feof(stdin))return;
			t++;
			scanf("%d",&a[t]);
		}
		scanf("\n");
	}
}


void	starmain()
{	
	int		i,t;	
	memset(res,127,sizeof(res));
	res[0]=-0x7FFFFFFF;	
	
	x=0;
	dfs(1);
		
	
	for (i=1;i<=q[0];i++)
	{
		t=std::upper_bound(res,res+i,q[i])-res;
		res[t]=std::min(q[i],res[t]);
		if (t>ans)ans=t;
	}
	printf("%d\n",q[0]-ans);
}

int		main()
{
//	freopen("c:\\in.txt","r",stdin);	
	
	init();
	starmain();
	
	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