最长上升子序列LIS

发表于 | | 阅读量 | 次阅读

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

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

输入格式
1行，若干个整数（个数≤100000）

NOIP 原题数据规模不超过 2000。

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

输入输出样例
在这里插入图片描述
这里我们需要二分查找优化找子序列的过程，不过这道题变成了最长不上升子序列。
这个时候我们设dp[i]的意义为：长度为i的子序列中末尾的最大值，i相当于子序列的长度。可以想象一下，这个序列的最后一位如果数字越大，那么构成更长的不上升子序列的长度期望会更长。
比如：6 4 2 1和6 4 3 2 两个序列，末尾越大越有可能会构成更长的子序列。

首先我们让dp[1]=a[1]，接着开始往后枚举，我们每枚举一个就要判断dp中最后一位(dp[len])和a[i]的大小，如果a[i]更小，那么它可以作为这个子序列的下一项，（这里我们用len）也就是dp[++len]=a[i];如果a[i]大于dp[len]，就要使用二分法找到dp序列中小于a[i]的第一位，然后替换，这里换成了比原来大的数。
比如：9 7 5 4 2 然后下一位是3，那么我们换掉比3小的第一位，也就是2，这时候，序列变成了9 7 5 4 3。

以此类推，遍历到最后，dp的长度len就是最长不上升子序列的长度。
第二问的话，可能不好理解，因为如果有两枚导弹，第一枚先来，第二枚后来，而第一枚的高度比第二枚低，那么必须要两台才行，如果后面还有一枚导弹比第二枚导弹还要高，不就要三台了吗……以此类推。

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<iostream>
using namespace std;
int a[100010];
int p[100010];
int b[100010];
int main()
{
    int i=0,len1=0,ans;
    while(~scanf("%d",&a[++i]));//循环输入
    int n=i-1;//最后一次没有输入因此跳出循环，n=i-1
    b[0] = 100000 ;
    b[++len1]=a[1];
    for(i=2;i<=n;i++){
        if(a[i]<=b[len1]){
            b[++len1]=a[i];
        }
        else 
        {
            int l=0,r=len1,mid;
            while(l<=r){
                mid=l+(r-l)/2;
                if(a[i]<=b[mid]){
                    ans=mid;
                    l=mid+1;
                }
                else r=mid-1;
            }
            b[ans+1]=a[i];
        }
        /*for(int j=1;j<=len1;j++){
                cout<<b[j]<<' ';
            }
            cout<<endl;*/
    }
    cout<<len1<<endl;
    int sum=0;
    int m=0;
    while(m<n){
        int last=10000000;
        for(int j=1;j<=n;j++){
            if(a[j]>0 && a[j]<=last){
                m++;
                last=a[j];
                a[j]=-1;
            }
        }
        sum++;
    }
    cout<<sum;
}
赞助一下作者啦
0%