pku1887.cpp

来自「这是ACM 方面的资料 是PKU的 北京大学的出来的」· C++ 代码 · 共 47 行

#include <stdio.h>
#define SIZE 5000

int Num[SIZE], DP[SIZE];
int Max;

int MAX(int x, int y)
{
	return x > y ? x : y;
}

int main()
{
	int p, i, j, L, t = 0;
	while (scanf("%d", &p) != -1 && p != -1)
	{
		Num[0] = p;
		i = 1;
		while (scanf("%d", &p) != -1 && p != -1)
		{
			Num[i++] = p;
		}
		L = i;
		for (i = 0; i < L; i++)
			DP[i] = 1;
		DP[0] = 1;
		Max = 1;
		for (i = 1; i < L; i++)
		{
			for (j = i - 1; j >= 0; j--)
			{
				if (Num[i] < Num[j])
				{
					DP[i] = MAX(DP[j] + 1, DP[i]);
					if (DP[i] > Max)
					{
						Max = DP[i];
					}
				}
			}
		}
		printf("Test #%d:\n  maximum possible interceptions: %d\n\n", ++t, Max);
	}
	return 0;
}