1952.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include <stdio.h>
#include <vector>
#include <algorithm>
#include <memory.h>
using namespace std;


int a[5001];
int s[5001],n,m;
int ans[5001];

vector<int> h[5001];


void doit()
{
	int i, j, k, answer;
	scanf( "%d", &n );

	for( i=0; i<n; i++ )
	{
		scanf( "%d", a+i );
		a[i] = -a[i];
		h[i].clear();
	}

	m = 0;
	
	for( i=0; i<n; i++ )
	{
		j = lower_bound( s, s+m, a[i] ) - s;
		s[j] = a[i];

		if( j == m )m++;

		
		if( j == 0 )ans[i] = 1;
		else
		{
			ans[i] = 0;
			for( k=0; k<h[j].size(); k++ )
			if( a[ h[j][k] ] < a[i] )
				ans[i] += ans[ h[j][k] ];
		}

		for( k=0; k<h[j+1].size(); k++ )
		if( a[i] == a[ h[j+1][k] ] )
		{
			ans[ h[j+1][k] ] = ans[i];
			break;
		}

		if( k == h[j+1].size() )
		h[j+1].push_back( i );
	}

	answer = 0;
	for( i=0; i<h[m].size(); i++ )
	answer += ans[  h[m][i] ];

	printf( "%d %d\n", m, answer );
	
}

int main()
{
	doit();
	return 0;
}