洛谷P1020 导弹拦截(线性DP)

题目描述

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

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

输入输出格式

输入格式：

1行，若干个整数（个数 ≤100000）

输出格式：

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

输入输出样例

样例输入

389 207 155 300 299 170 158 65

样例输出

6
2

思路：

第一个问题是求这套系统最多能拦截的导弹数，也就是求一个最长非上升子序列的长度，第二个问题比较巧妙，求得是最少要配备多少套这种导弹拦截系统，其实就是求一个最长上升子序列的长度，因为最长上升子序列的长度每加1就要多一套系统来拦截。
求最长上升子序列问题肯定是用DP啦，不过这题数据范围有1e5所以O(n*n)的普通做法最后的100分过不了，会TLE。所以本题要用O(nlgn)的做法，利用最长上升子序列的单调性来降低时间复杂度。

O(n*n)的100分代码

#include <bits/stdc++.h>

using namespace std;

int dp[100010];
int num[100010];

int main(){
    int i = 0,len = 0;
    while(scanf("%d",&num[i]) != EOF){
        i++;
    }
    memset(dp,0,sizeof(dp));
    for(int j = 0;j<i;j++){
        for(int k = 0;k<j;k++){
            if(num[j]<=num[k]){
                dp[j] = max(dp[j],dp[k]+1);
                len = max(dp[j],len);
            }
        }
    }
    cout<<len+1<<endl;
    memset(dp,0,sizeof(dp));
    len = 0;
    for(int j = 0;j<i;j++){
        for(int k = 0;k<j;k++){
            if(num[j]>num[k]){
                dp[j] = max(dp[j],dp[k]+1);
                len = max(dp[j],len);
            }
        }
    }
    cout<<len+1;
    return 0;
}

O(nlgn)的200分代码

#include <bits/stdc++.h>

using namespace std;

const int INF = 0x3f3f3f3f;

int dp[100010];
int num[100010];
int b[100010];

int main(){
    int i = 0,k = 0;
    while(scanf("%d",&num[i]) != EOF){
        i++;
    }
    for(int j = i-1;j>=0;j--)
        b[k++] = num[j];
    fill(dp,dp+i,INF);
    for(int j = 0;j<i;j++){
        int pos = upper_bound(dp,dp+i,b[j]) - dp;
        dp[pos] = b[j];
    }
    cout<<lower_bound(dp,dp+i,INF)-dp<<endl;
    fill(dp,dp+i,INF);
    for(int j = 0;j<i;j++){
        int pos = lower_bound(dp,dp+i,num[j]) - dp;
        dp[pos] = num[j];
    }
    cout<<lower_bound(dp,dp+i,INF) - dp<<endl;
    return 0;
}