难度：普及/提高-

题目描述

        某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。

        输入导弹依次飞来的高度(雷达给出的高度数据是≤50000的正整数)，计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

输入输出格式

输入格式:

        1行，若干个整数(个数≤100000)

输出格式:

        2行，每行一个整数，第一个数字表示这套系统最多能拦截多少导弹，第二个数字表示如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

输入输出样例

Sample input

389 207 155 300 299 170 158 65

Sample output

6
2

题解

未强化版本:
        经典的求最长上升(下降…)子序列问题，属于线型动态规划。
        第一问即求序列中最长不上升子序列的长度，第二问即求序列中最少的最长不上升子序列数量。由Dilworth定理，该问即为求序列的最长上升子序列长度。
        设f(x)为以第x个数为序列起点，可得到的最长序列长度。
        则对于第一问，状态转移方程为:

        第二问为:

        n表示序列总长度，value[x]表示第x个元素的值。时间复杂度O(n2)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include<iostream>

using namespace std;
int n, op[100005], dp1[100005] = {0}, dp2[100005] = {0};

int main() {
    int p = 1, ans1 = 0, ans2 = 0;
    while (cin >> op[p])p++;
    n = p - 1;
    for (register int i = n; i >= 1; i--) {
        int t = 0;
        for (register int j = i + 1; j <= n; j++) {
            if (op[i] >= op[j])t = max(t, dp1[j]);
        }
        dp1[i] = t + 1;
        ans1 = max(dp1[i], ans1);
    }
    for (register int i = n; i >= 1; i--) {
        int t = 0;
        for (register int j = i + 1; j <= n; j++) {
            if (op[i] < op[j])t = max(t, dp2[j]);
        }
        dp2[i] = t + 1;
        ans2 = max(dp2[i], ans2);
    }
    cout << ans1 << endl << ans2;
    return 0;
}

强化版本:
        由于数据量过大，考虑到O(n2)会造成超时，下面介绍O(nlogn)求子序列长度方法。
        此处考察贪心和二分思想。
        以上升序列为例，取ans[x]表示当前长度为x的子序列末尾的最小值，这个值较小时，可以保证更长的序列长度。这是正确的贪心策略。
        易知，ans[x]为严格单增序列。这是因为倘若ans[x]>ans[x+1]，则ans[x+1]完全可以成为长度为x的上升子序列的末尾，这与ans[x]表示最小值矛盾。倘若ans[x]=ans[x+1]，在ans[x+1]所在的子序列中截取前x项，则末项m < ans[x+1]=ans[x]，此时m为一个长度为x的子序列的末尾，仍与ans[x]的最小性矛盾。
        于是，维护ans[x]序列，置ans[1]=value[1]进行初始化，对于之后的每一个值，我们用二分查找在ans[x]中(利用ans[x]的单调性)找到第一个不比其小的数，按照ans[x]的定义进行修改。最终ans[x]的长度即为最长上升子序列的长度。
        对于每一个待加入数m，维护ans[x]的方法就是把m加入ans[x]又不违反ans[x]的定义。显然，对于ans[p]≥m，m均不会成为长度为p(或大于p)的序列的末尾，于是寻找ans[p] < m。然而，倘若ans[p+1] < m，则即使将m加入长度为p的序列末尾，m也不是最小值，违反了ans[x]定义。综上所述，我们要寻找第一个不小于m的ans[p]使ans[p]=m。若所有ans[x]均小于m，则令ans[x]长度加一，末尾置m。
        不上升子序列与之同理，这里不再赘述。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<iostream>

using namespace std;
int op[100001], ans1[100000] = {0}, ans2[100000] = {0};

int find1(int x, int l, int r) {
    if (r == l + 1)return r;
    int mid = (l + r) / 2;
    if (ans1[mid] >= x)return find1(x, mid, r);
    else return find1(x, l, mid);
}

int find2(int x, int l, int r) {
    if (r == l + 1)return r;
    int mid = (l + r) / 2;
    if (ans2[mid] >= x)return find2(x, l, mid);
    else return find2(x, mid, r);
}

int main() {
    int p = 1;
    while (cin >> op[p])p++;
    op[0] = p - 1;
    int res1 = 1, res2 = 1;
    ans1[1] = op[1];
    for (register int i = 2; i <= op[0]; i++) {
        if (ans1[res1] >= op[i])ans1[++res1] = op[i];
        else ans1[find1(op[i], 0, res1)] = op[i];
    }
    ans2[1] = op[1];
    for (register int i = 2; i <= op[0]; i++) {
        if (ans2[res2] < op[i])ans2[++res2] = op[i];
        else ans2[find2(op[i], 0, res2)] = op[i];
    }
    cout << res1 << endl << res2;
    return 0;
}