题解 P2757 【导弹的召唤(数据加强)】

· · 题解

啊，终于有了一道算是nlogn的LIS模板题了，我的LIS终于可以拉出来卡n^2的了~~【什么心态啊喂~】

好吧，反正思路基本就是贪心，末尾大的一般要优，所以记录一下当前的，如果大就往后扔，不然二分查找一下插到里面……

STL大法好，lower_bound太好用了喂~

下面上代码，压行有点厉害，大家凑合着看，不喜勿喷。

···cpp

#include<iostream>
#include<algorithm>
using namespace std;
#define N 300000
int a[N+1],b[N+1]={-1},n,x,y;
bool cmp(const int &a,const int &b)
{
    return a>b;
}
int main()
{
    while(cin>>a[n++]);n--;
    for(int i=0;i<n;i++)
        a[i]<=b[y]?b[++y]=a[i]:b[upper_bound(b,b+y,a[i],cmp)-b]=a[i];
//三目运算符压行系列，第一问是个不下降大家都理解吧，所以要带一个比较函数，
//因为不下降所以可以相等，upper_bound就用上了。。
    cout<<y+1<<endl;
    b[0]=-1;for(int i=1;i<=n;i++) b[i]=0;
    for(int i=0;i<n;i++)
        a[i]>b[x]?b[++x]=a[i]:b[lower_bound(b,b+x,a[i])-b]=a[i];
    cout<<x;
//第二问哪里需要贪心嘛，人类需要LIS（最长上升子序列）
//第二问是个纯上升嘛，上板子就好啦~
//搞定
}