【51nod】3111 小明爱拦截

本文主要是介绍【51nod】3111 小明爱拦截，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

小明爱拦截

Link

---

解题思路

导弹拦截的一半操作，求最长不上升子序列。
每个数取负，当成最长不下降子序列来做。
贪心把每个数塞入序列中，二分找位置或加入尾部、答案 $++$。

code

#include<algorithm>
#include<iostream>
#include<cstdio>
using namespace std;int n,ans,t;
int a[100010];int main()
{cin>>n>>t;a[++ans]=-t;for(int i=2;i<=n;i++){scanf("%d",&t);if(-t>=a[ans])a[++ans]=-t;elsea[upper_bound(a+1,a+ans+1,-t)-a]=-t;}cout<<ans<<endl;
}

这篇关于【51nod】3111 小明爱拦截的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---