AcWing 1010. 拦截导弹
原题链接
简单
作者:
wangyj
,
2021-01-12 17:57:54
,
所有人可见
,
阅读 260
#include<sstream>
#include<iostream>
#include<algorithm>
using namespace std;
int n,h[1005],f[1005],q[1005];
int main()
{
string line;
getline(cin,line);
stringstream ssin(line);
while(ssin>>h[n])n++;
int ans=0,cnt=0,i,j,k;
for(i=0;i<n;i++){
f[i]=1;
for(j=0;j<i;j++)if(h[i]<=h[j])f[i]=max(f[i],f[j]+1);
ans=max(ans,f[i]);
k=0;
while(k<cnt&&q[k]<h[i])k++;
if(k==cnt)q[cnt++]=h[i];
else q[k]=h[i];
}
printf("%d\n",ans);
printf("%d\n",cnt);
return 0;
}