洛谷P1020：导弹拦截

P1020 [NOIP1999 普及组] 导弹拦截 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

这道题其实是两个问题的结合，可以互不干扰地求出。

第一个问题，NOPI里是可以用o(n^2)的时间复杂度算出来，但是洛谷提高了要求，得用o(nlogn)的时间复杂度求出来。

那我先介绍时间复杂度为n^2的dp算法。

写dp前先确认每个阶段的含义，这里我们定义每个阶段的含义为：以第i个数字为结尾的最长非增子串。

我们把每个阶段的决策抽象为一个点，那么我们先确认一下每个点的决策依据，即父节点。

我们可以很容易地想出我们可以遍历第i个点前面的点j，并在满足条件

下找到最大值。

那么接下来就是代码了。

#include<iostream>
#include<algorithm>
using namespace std;

const int N=100010;

int st[N];//存储每个数
int dp[N];//dp[i]为以i为结尾的最长子串的长度
int ans;
int n;

int main(){
    
    cin>>n; 
    
    for(int i=1;i<=n;i++) scanf("%d",&st[i]);
    
    for(int i=1;i<=n;i++){//遍历每个阶段
        
        if(i==1) dp[i]=1;
        
        int a=0;
        
        for(int j=i-1;j>0;j--){//找到最优决策
            
            if(st[i]<=st[j])
                a=max(a,dp[j]);
            
        }
        dp[i]=a+1;
        ans=max(ans,dp[i]);
        
    }
    
    cout<<ans;
}

那么接下来就是nlogn的算法了。

这个时候我们每个dp的含义就变了，dp[i]为长度为i时最大高度，并且用一个数len来记录当前最大的长度。

那么我们就确认每个阶段的父节点是什么，从dp数组的实际含义出发，我们只需要遍历每个点，然后利用该点的数值更新dp数组，即当数值小于dp[len]时我们让dp[len+1]=st[i]，并且让len++，如果否的话，我们就寻找长度最小的，且结尾数小于st[i]的，并将其更新为st[i]，这里因为dp数组是严格非增的，所以我们可以用二分来寻找这个数。

下面是具体代码；

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;

const int N=100010;

int dp[N],len=0;
int st[N];
int n;




int main(){
    
    while(scanf("%d",&st[n])!=EOF) n++;
    
    memset(dp,0x3f3f3f3f,sizeof dp);//先将每个数都初始化到足够大
    
    for(int i=0;i<n;i++){//遍历每个数，并依次更新dp数组
        
        if(st[i]<=dp[len]) dp[++len]=st[i];//当小于当前最大长度里存储的数时，我们将长度+1，并赋值

        else{//二分找到对应的下标
            
            int l=0,r=len;
            
            while(l<r){
                
                int mid=l+r+1>>1;
                
                if(st[i]<=dp[mid]) l=mid;
                else r=mid-1;
                
            }
            
            dp[l+1]=st[i];//l为长度最大且dp[l]>=st[i]的下标，l+1即为长度最小且dp[l+1]<st[i]的下标
            
        }
        
    }
    
    cout<<len<<endl;
    
    
}

那么接下来就是解决另外一个问题了，即求序列在最少可以排列出多少个非增子序列。

具体的话可以看代码，因为本菜鸟时间紧张，所以就不细说了，可以拿一个案例来模拟一下。

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;

const int N=100010;

int st[N];
int n;
vector<int> p;

void get(int x){
    
    int rcod=-1;
    
    for(int i=0;i<p.size();i++){
        
        if(x<=p[i]){
            
            if(p[rcod]>=p[i]||rcod==-1)
            rcod=i;
            
        }
        
    }
    
    if(rcod!=-1) p[rcod]=x;
    else p.push_back(x);
    
}


int main(){
    
    while(scanf("%d",&st[n])!=EOF) n++;
    
    p.push_back(st[0]);
    
    for(int i=1;i<n;i++){
        
        get(st[i]);
        
    }
    
    cout<<p.size();
    
}