POJ 1887 Testing the CATCHER G++
程序员文章站
2022-07-15 10:46:19
...
#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;
}