AcWing 1010. 拦截导弹
原题链接
简单
作者:
徐学神
,
2023-02-06 13:40:43
,
所有人可见
,
阅读 100
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e3+10;
ll n,tmp,k,j,a[N],s[N],dp[N],ans;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
while(cin>>tmp) a[++n]=tmp;
for(ll i=1;i<=n;i++) {
dp[i]=1;
for(j=1;j<i;j++) {
if(a[j]>=a[i]) dp[i]=max(dp[i],dp[j]+1);
}
ans=max(ans,dp[i]);
}
cout<<ans<<"\n";
for(ll i=1;i<=n;i++) {
for(j=1;j<=k;j++) {
if(s[j]>=a[i]) {
s[j]=a[i];
break;
}
}
if(j>k) s[++k]=a[i];
}
cout<<k;
return 0;
}