题意：题目太长没看，直接看输入输出猜出是最长下降子序列

用了以前的代码直接a了，做法类似贪心，把最小的顺序数存在数组里面，每次二分更新数组得出最长上升子序列

#include<iostream>

#include<cstdio>

using namespace std;

int main()

{

	int dp[40002],a[40002],n,t,i,low,up,top,mid,max,tmp,k,b[40002],cas=1;

	while(1)

	{

		scanf("%d",&tmp);

		if(tmp==-1)

			break;

		k=1;

		b[k++]=tmp;

		while(scanf("%d",&tmp)){

			if(tmp==-1)

				break;

			b[k++]=tmp;

		}

		k--;

		for(i=1;i<=k;i++)

			a[i]=b[k-i+1];

		top=1;

		dp[1]=a[1];

		max=0;

		for(i=1;i<=k;i++)

		{

			low=1;

			up=top;

			while(low<=up)

			{

				mid=(low+up)/2;

				if(dp[mid]>=a[i])

					up=mid-1;

				else

					low=mid+1;

			}

			dp[low]=a[i];

			if(low>top)

				top++;

		}

		printf("Test #%d:\n",cas++);

		printf("  maximum possible interceptions: %d\n\n",top);

	}

	return 0;

}