P1020 导弹拦截

第一个数字表示这套系统最多能拦截多少导弹，第二个数字表示如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

1. 最长不上升序列
2. 最长上升序列

\(dp_{i}=\max(1,\max\limits_{j<i,h(j)>h(i)}\{dp_{j}+1\})\)

#include <bits/stdc++.h>
using namespace std;
int a[100010], d[100010];
int main()
{
    int x;
    int size = 0;
    while (cin >> x)
        a[++size] = x;
    //----------------最长不上升序列
    d[1] = a[1];
    int len = 1;
    for (int i = 2; i <= size; i++)
    {
        if (a[i] <= d[len])
            d[++len] = a[i];
        else
        {
            int pos = upper_bound(d + 1, d + 1 + len, a[i], greater<int>()) - d;
            d[pos] = a[i];
        }
    }
    cout << len << '\n';
    //----------------最长上升序列
    d[1] = a[1];
    len = 1;
    for (int i = 2; i <= size; i++)
    {
        if (a[i] > d[len])
            d[++len] = a[i];
        else
        {
            int pos = lower_bound(d + 1, d + 1 + len, a[i]) - d;
            d[pos] = a[i];
        }
    }
    cout << len << endl;
}