<—点个赞吧QwQ

宣传一下算法提高课整理

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

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

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

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

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

输入格式

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

输出格式

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

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

数据范围

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

输入样例：

389 207 155 300 299 170 158 65

输出样例：

6
2

思路

我们每次只能拦截高度递减的导弹，所以第一问的解就是整个序列的最长下降子序列。
对于第二问，我们使用贪心算法，假设我们已经算出前$i-1$个数的最长上升子序列了，假设每一个最长上升子序列的最后一个数保存在$g$数组里，比如$g_k$表示第$k$个最长上升子序列的最后一个数。每次插入一个数（假设是$x$），我们贪心的把这个数插到一个上升子序列的最后一个数（假设是$a$）后面，使得$a < b$并且$a$最大。
假设贪心解得到的答案是$A$，最优解得到的答案是$B$
由于贪心解一定是合法解，所以$A\geq B$
如果贪心解与最优解不同，那么做那个能找到一个位置，使得当前数（设为$x$）在贪心解插到了一个数后面（假设是$a$），而最优解插到了另一个数的最后面（假设是$b$），由于$a$是最小的结尾数，所以$b>a$。所以在最终答案中，$a$后面$x$以及$x$后面的所有数可以与$b$后面的所有数交换，并且答案不变。所以贪心解不差于最优解，即$A\leq B$，所以$A=B$。
这里我们得到的贪心解一定等于最优解，经过观察，我们可以发现这里的$g$数组，与最长上升子序列$\text{II}$的$\text{DP}$数组是类似的，所以求解$g$数组的过程等价于求最长上升子序列。
讲了这么多，上代码吧。

代码

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int n = 0;
int a[N],f[N];
int main () {
    while (cin >> a[n + 1]) n++;
    int ans = 0;
    for (int i = 1;i <= n;i++) {
        f[i] = 1;
        for (int j = 1;j < i;j++) {
            if (a[j] >= a[i]) f[i] = max (f[i],f[j]+1);
        }
        ans = max (ans,f[i]);
    }
    cout << ans << endl;
    ans = 0;
    for (int i = 1;i <= n;i++) {
        f[i] = 1;
        for (int j = 1;j < i;j++) {
            if (a[j] < a[i]) f[i] = max (f[i],f[j]+1);
        }
        ans = max (ans,f[i]);
    }
    cout << ans << endl;
    return 0;
}