poj1887——Testing the CATCHER

求最长递减子序列 ——>转化成求最长递增子序列！

#include<iostream>
#include<cstdio>
#define maxn 33000
int g[maxn],stack[maxn],ans;
int research(int l,int r,int p)
{
	if(l==r )return r;
	int mid=(l+r)>>1;
	if(p<stack[mid]) 
		return research(l,mid,p);
	else return research(mid+1,r,p);
}
int main()
{
	int i,j,n,ca=1,k;
	while(1)
	{
		scanf("%d",&k);
		if(k==-1)
			break;
		n=0;g[0]=k;
		while(1)
		{
			scanf("%d",&k);
			if(k!=-1) { g[++n]=k;}
			else 
			{
				stack[0]=g[n];ans=1;
				for(i=n-1;i>=0;i--)
				{
					if(g[i]>stack[ans-1]) stack[ans++]=g[i];
					else 
					{
						int mid=research(0,ans-1,g[i]);
						if(g[i]<stack[mid]) stack[mid]=g[i];
						else stack[mid+1]=g[i];
					}
				}
				printf("Test #%d:\n",ca++);
				printf("  maximum possible interceptions: %d\n\n",ans);
				break;
			}
		}
	}
	return 0;
}