1887.txt

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

#define debug 0
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#define NMAX 5000
#define INF 1000000001
int a[NMAX],m[NMAX];
int  N;
int tmax;
void solve()
{
	
	int i,j;
	m[0]=1;
	tmax=1;
	for(i=1;i<N;i++)
	{
		m[i]=1;
		for(j=0;j<i;j++)
		{
			if(a[j]>=a[i]&&m[j]+1>m[i])
			{
				m[i]=m[j]+1;
			}
		}
		if(tmax<m[i])
			tmax=m[i];
	}
}
main()
{
#if debug 	
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
#endif
	long i,t;
	t=1;
	scanf("%d",&a[0]);
	while(a[0]!=-1)
	{
		i=1;
		while(1)
		{
			scanf("%d",&a[i]);
			if(a[i]==-1)
			{
				break;
			}
			i++;
		}
		N=i;
		solve();
		printf("Test #%d:\n  maximum possible interceptions: %d\n\n",t++,tmax);
		scanf("%d",&a[0]);
	}

#if debug
	fclose(stdin);
	fclose(stdout);
#endif;
	return 1;
}