洛谷 P1020 导弹拦截

很经典的DP题

不会

原题链接：https://www.luogu.org/problem/P1020

俩问：一是求最长不上升子序列长度

二是求最长上升子序列长处

看了一个大佬的题解，学了一种O(nlogn)的解法

以下是dalao原话：
首先我们需要一个数组a，存储从第1个到第n个导弹的高度

然后一个数组d(其实是个栈)，存储不上升序列

把a中的每个元素挨个加到d里面：

(a中第i个元素为a[i]，d长度为len，d中最后一个(也是最小的一个)为d[len])

如果a[i] <= d[len]，说明a[i]可以接在d后面(而整个d还是有序的)，那就简单粗暴地把a[i]丟进d：

如果a[i] > d[len]，说明a[i]接不上

但是我们发扬瞎搞精神：接的上要接，接不上创造条件也要接！

强行把a[i]塞进去：

在d中找到第一个小于a[i]的数，把它踹了，用a[i]代替它！(为什么正确在下面）

假设这个数是y，怎样踹掉它呢？

很明显，我们需要使用lower_bound和upper_bound来查找

为什么正确

显然成立

如果y在末尾，由于y < a[i]，所以y后面能接的不如a[i]多，y让位给a[i]可以让序列更长

如果y不在末尾，那y有生之年都不会再被用到了，直接踹了y就行，y咋样，who care？

#include <bits/stdc++.h>
using namespace std;
int a[100100];
int e[100100];
int c[100100];
int main()
{
    int l=0;
    while(~scanf("%d",&a[++l]));
    l--;
    int xp=0,cp=0;
    e[xp++]=a[1];
    c[cp++]=a[1];
    for(int i=2;i<=l;i++)
    {
        if(a[i]<=e[xp-1])
        {e[xp++]=a[i];}
        else
        {
            int op=upper_bound(e,e+xp,a[i],greater<int>())-e;
            e[op]=a[i];
        }
        if(a[i]>c[cp-1])
        {c[cp++]=a[i];}
        else
        {
            int op=lower_bound(c,c+cp,a[i])-c;
            c[op]=a[i];
        }
    }
    cout<<xp<<endl<<cp;
    return 0;
} 

123