欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

POJ 1887 Testing the CATCHER G++

程序员文章站 2022-07-15 10:46:19
...

POJ 1887 Testing the CATCHER G++

POJ 1887 Testing the CATCHER G++

POJ 1887 Testing the CATCHER G++

#include <iostream>
#include <map>
#include <algorithm>
using namespace std;
map<int,int> dp;
int main()
{
	int flag=0;
	int tag=0;
	while(1)
	{
		tag++;
		int jg=0;
		dp.clear();
		while(1)
		{
			int a;
			cin>>a;
			if(a!=-1)
			{
				flag=1; 
			} 
			if(a==-1 && flag==0)
			{
				return 0;
			}
			if(a==-1 && flag==1)
			{
				cout<<"Test #"<<tag<<":"<<endl;
				cout<<"  maximum possible interceptions: "<<jg<<endl<<endl;
				break;
			}
			/*
			for(map<int,int>::reverse_iterator it=dp.rbegin();it!=dp.rend();it++)
			{
				cout<<"test "<<it->first<<" "<<it->second<<endl;
			}*/	
			int tmp=0;		
			for(map<int,int>::reverse_iterator it=dp.rbegin();it!=dp.rend();it++)
			{
				if(it->first>=a)
				{
					//cout<<"it "<<it->first<<" "<<it->second<<endl;
					tmp=max(tmp,it->second+1);
				}else
				{
					break;
				}
			}
			dp[a]=max(tmp,1);
			//cout<<"dp "<<a<<" "<<dp[a]<<endl;
			jg=max(jg,dp[a]);
		}
		flag=0;		
	}
	
	return 0;
}