拦截导弹 https://www.acwing.com/problem/content/1012/
NOIP1999

第一发炮弹可以打任意高度，后面的炮弹不能高于第一发
1.若只有一台大炮，最多能拦截多少导弹 -> 寻找最长下降子序列
2.最少需要多少台大炮，可以将所有导弹拦截 -> 贪心

第一个导弹之后的每个导弹有两个选择
1.接在现有的子序列之后
2.创建新的子序列
-> 无论哪种选择，操作完后该导弹一定是现有子序列结尾
争取让剩下的子序列的结尾尽可能大

-> 将该导弹接到结尾大于该导弹最小的序列之后
   若子序列结尾都小于该导弹，则新开一个子序列

贪心流程：
从前往后扫描每个数，对于每个数
如果现有子序列结尾都小于当前数 - 创建新子序列
存在子序列结尾大于等于当前数 - 将当前数放到结尾大于等他的最小的子序列

证明：
最优解子序列个数小于贪心法子序列个数 B <= A
假设x是最优解方案和贪心方案第一个不同的数
最优解方案 - x接在b
贪心方案 - x接在a
一定有 b >= a
全部接完后，因 x >= b 且 b >= a ,可以将两种方案x及后面的数交换
交换后子序列数量不变，也还是合法方案
即只要最优解和贪心法方案不一样，找到第一个不一样的数，可以进行交换
即贪心法得到的子序列个数，小于等于最优解子序列个数 A <= B
-> A = B

#include <iostream>
using namespace std;

const int N = 1010;
int f[N], g[N], a[N], n, res, cnt;

int main()
{
    while ( cin >> a[n] ) n ++;
    for ( int i = 0; i < n; i ++ )
    {
        f[i] = 1;
        for ( int j = 0; j < i; j ++ )
            if ( a[i] <= a[j] ) f[i] = max(f[i], f[j] + 1);
        res = max(res, f[i]);

        int k = 0;
        while ( k < cnt && g[k] < a[i] ) k ++;
        g[k] = a[i];
        if ( cnt == k ) cnt ++;
    }
    cout << res << endl << cnt;
    return 0;
}