题目描述

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

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

输入格式

11行，若干个整数（个数 \le 100000≤100000）

输出格式

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

输入输出样例

输入

1
389 207 155 300 299 170 158 65

输出

1
2
6
2

题解

第一个要输出的显而易见是最长非上升子序列， 但是第二问就有意思了， 是求最长上升子序列。

ac代码：

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
38
39
40
41
42
43
44
45
46
47
48
49
50
//#include <bits/stdc++.h>
#include <iostream>
#include <stack>
#include "algorithm"
#include "cstdio"
#include "queue"
#include "set"
#include "cstring"
#include "string"
#include "map"
#include "vector"
#include "math.h"
#include "utility"   // pair头文件
#define esp 1e-6
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int INF = 0x3f3f3f3f;
const int N = 1e6 + 5;
const int M = 1e9 + 5;

int a[N];

int dp1[N], dp2[N], len1, len2;
int main(){
    int n = 1;
    char c;
    while(cin >> a[n]){
        c = getchar();
        if (c != ' ')
            break;
        n++;
    }
    len1 = len2 = 1;
    dp1[1] = dp2[1] = a[1];
    for (int i = 2; i <= n; i++){
        if (a[i] <= dp1[len1])
            dp1[++len1] = a[i];
        else
            *upper_bound(dp1 + 1, dp1 + len1 + 1, a[i], greater<int>()) = a[i];
        if (a[i] > dp2[len2])
            dp2[++len2] = a[i];
        else
            *lower_bound(dp2 + 1, dp2 + len2 + 1, a[i]) = a[i];
    }

    printf("%d\n%d\n", len1, len2);

    return 0;
}

具体关于lis的总结： 请戳此

1
恰似你一低头的温柔，娇弱水莲花不胜寒风的娇羞， 我的心为你悸动不休。  --mingfuyan