洛谷 P1020 导弹拦截

题目链接：导弹拦截

思路

代码

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

const int N = 1e5 + 5;
int a[N], x, l, dp[N], maxn;
int g[N], cnt;

int main() {
    while (cin >> x) a[++l] = x;
    for (int i = 1; i <= l; i++) {
        int k = 1;
        while (k <= cnt && g[k] >= a[i]) k++;
        if (k > cnt) g[++cnt] = a[i];
        else g[k] = a[i];
    }
    cout << cnt << endl;
    cnt = 0;
    for (int i = 1; i <= l; i++) {
        int k = 1;
        while (k <= cnt && g[k] < a[i]) k++;
        if (k > cnt) g[++cnt] = a[i];
        else g[k] = a[i];
    }
    cout << cnt << endl;
}