P1020 [NOIP 1999 提高组] 导弹拦截

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    vector<int> a;
    int x;
    while (cin >> x) a.push_back(x);

    // 第一问：最多能拦截多少发 = 最长不升子序列长度。
    // t1[k] = 长度为 k+1 的不升子序列，末尾高度最大能取到多少（保持单调不升）。
    vector<int> t1;
    for (int h : a) {
        auto it = upper_bound(t1.begin(), t1.end(), h, greater<int>());
        if (it == t1.end()) t1.push_back(h);
        else *it = h;
    }

    // 第二问：最少要几套系统 = 最长严格上升子序列长度（Dilworth 定理）。
    // t2[k] = 长度为 k+1 的严格上升子序列，末尾高度最小能取到多少（保持严格上升）。
    vector<int> t2;
    for (int h : a) {
        auto it = lower_bound(t2.begin(), t2.end(), h);
        if (it == t2.end()) t2.push_back(h);
        else *it = h;
    }

    cout << t1.size() << "\n" << t2.size() << "\n";
    return 0;
}