pku1952.cpp

这是ACM 方面的资料 是PKU的 北京大学的出来的

#include <stdio.h>
#define size 5100
int val[size], length[size], sum[size], save[size];
int N;
int main()
{
	int i, j, max, cnt, k;
	while (scanf("%d", &N) != -1 && N)
	{
		for (i = 0; i < N; i++)
		{
			scanf("%d", &val[i]);
			length[i] = 1;
			sum[i] = 1;
		}
		val[N] = -10000000;
		N++;
		max = 1;
		for (i = 0; i < N; i++)
		{
			length[i] = 1;
			for (j = 0; j < i; j++)
			{
				if (val[i] < val[j] && length[i] < length[j] + 1)
				{
					length[i] = length[i] + 1;
				}
			}
			if (length[i] == 1)
			{
				sum[i] = 1;
			}
			else
			{
				sum[i] = 0;
				cnt = 0;
				for (j = i - 1, cnt = 0; j >= 0; j--)
				{
					if (val[j] > val[i] && length[j] + 1 == length[i])
					{
						for (k = 0; k < cnt; k++)
						{
							if (val[j] == save[k])
							{
								break;
							}
						}
						if (k == cnt)
						{
							save[cnt++] = val[j];
							sum[i] += sum[j];
						}
					}
				}
			}
		}
		printf("%d %d\n", length[N - 1] - 1, sum[N - 1]);
	}
	return 0;
}