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

贴代码

Posted by fatfish at 2013-03-12 00:51:43 on Problem 3298
// 类似于最长上升子序列

#include <stdio.h>
#include <string.h>

const int maxN = 30006;
int data[maxN];
int rank[maxN];
int n;

void inputData()
{
	scanf("%d", &n);
	for (int i = 0; i < n; ++ i)
	{
		scanf("%d", &data[i]);
	}
}

void process()
{
	memset(rank, 0, sizeof(rank));
	rank[0] = 0;
	rank[1] = data[0];
	int rLen = 2;
	for (int i = 1; i < n; ++ i)
	{
		for (int j = rLen - 1; j >= 0; -- j)
		{
			if (j & 1)
			{
				if (rank[j] > data[i])
				{
					if (j == rLen - 1)
					{
						rank[rLen] = data[i];
						++ rLen;
					}
					else if (rank[j + 1] > data[i])
					{
						rank[j + 1] = data[i];
					}
					break;
				}
			}
			else
			{
				if (rank[j] < data[i])
				{
					if (j == rLen - 1)
					{
						rank[rLen] = data[i];
						++ rLen;
					}
					else if (rank[j + 1] < data[i])
					{
						rank[j + 1] = data[i];
					}
					break;
				}
			}
		}
	}
	printf("%d\n", rLen - 1);
}

int main()
{
	int cases;
	scanf("%d", &cases);
	for (int i = 0; i < cases; ++ i)
	{
		inputData();
		process();
	}
	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