题目描述

某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。

但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。

某天，雷达捕捉到敌国的导弹来袭。

由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。

输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数，导弹数不超过1000），计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

输入格式

共一行，输入导弹依次飞来的高度。

输出格式

第一行包含一个整数，表示最多能拦截的导弹数。

第二行包含一个整数，表示要拦截所有导弹最少要配备的系统数。

数据范围

雷达给出的高度数据是不大于 30000 的正整数，导弹数不超过 1000。

样例

389 207 155 300 299 170 158 65

算法1 : 最长上升子序列 == 最少用多少个非上升子序列才能填满整个序列

到了这里，我们可以惊人地发现，似乎和最长上升子序列的贪心求法有异曲同工之妙。

而且，明明是要求至少需要多少个非上升子序列可以把整个序列填满，答案却恰恰是最长上升子序列的长度。

想来也不乏道理。初略来讲，对于一个最长上升子序列来说，是整个序列所有能构成上升序列的最长长度，假设该序列为 a b c d e，必然有前者严格小于后者的规则。

那么要想用非上升序列填满整个序列，显然，a、b、c、d、e 不可能处于同一个非上升（前者严格大于等于后者）子序列，故而至少需要 5 个非上升子序列，对应本题也就是至少需要 5 个拦截系统。

同理，最长下降子序列也对应着最少需要多少个非下降子序列才能填满。

当然，这也意味着，如若转换问题，那么题目的数据范围可达到 10 ^ 6，因为贪心解法为 nlogn （需要用到二分），具体可移步 第二点的 AcWing 896. 最长上升子序列 II（n = 10^5 nlogn的做法）。

时间复杂度 $O(n^2)$

C++ 代码

#include<bits/stdc++.h>

using namespace std;

const int N = 1010;
const int INF = 0x3f3f3f3f;

priority_queue<int> q;

int nums[N], down[N], up[N];

int main() {
    int a, n = 0;
    while (scanf("%d", &a) != EOF) nums[++ n] = a;
    //裸求最长非上升子序列
    int maxx = 0;
    nums[0] = INF;
    for (int i = 1; i <= n; ++ i) {
        for (int j = 0; j < i; ++ j) {
            if (nums[j] >= nums[i]) down[i] = max(down[i], down[j] + 1);
        }
        maxx = max(maxx, down[i]);
    }
    //裸求最长上升子序列
    int minn = -INF;
    nums[0] = -INF;
    for (int i = 1; i <= n; ++ i) {
        for (int j = 0; j < i; ++ j) {
            if (nums[j] < nums[i]) up[i] = max(up[i], up[j] + 1);
        }
        minn = max(minn, up[i]);
    }
    cout << maxx << endl << minn;
    return 0;
}

算法2 : 常规解法 + 大根堆

时间复杂度 $O(n^2)$

C++ 代码

#include<bits/stdc++.h>

using namespace std;

const int N = 1010;

priority_queue<int> q;

int nums[N], dp[N];

int main() {
    int a, n = 0;
    while (scanf("%d", &a) != EOF) {
        nums[++ n] = a;
        if (q.empty() || q.top() < a) q.push(a);
        else {
            stack<int> s;
            while (!q.empty() && q.top() >= a) {
                s.push(q.top());
                q.pop();
            } 
            s.pop();
            while (!s.empty()) {
                q.push(s.top());
                s.pop();
            }
            q.push(a);
        }
    }
    int maxx = 0;
    nums[0] = 0x3f3f3f3f;
    for (int i = 1; i <= n; ++ i) {
        for (int j = 0; j < i; ++ j) {
            if (nums[j] >= nums[i]) dp[i] = max(dp[i], dp[j] + 1);
        }
        maxx = max(maxx, dp[i]);
    }
    cout << maxx << endl << q.size();
    return 0;
}