HJ24 合唱队

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
void get_dp1(std::vector<int>& arr,int *dp,bool left2right=true){
    int n=arr.size();
    if(left2right){
        for(int i=0;i<n;i++){
            dp[i]=1;
            for(int j=0;j<i;j++){
                if(arr.at(i)>arr.at(j)){
                dp[i]=max(dp[i],dp[j]+1);
                }
            }
        }
    }else{
        for(int i=n-1;i>=0;i--){
            dp[i]=1;
            for(int j=n-1;j>i;j--){
                if(arr.at(i)>arr.at(j)){
                    dp[i]=max(dp[i],dp[j]+1);
                }
            }
        }
    }

}
void get_dp2(std::vector<int>& arr,int *dp,bool left2right=true){
    int n=arr.size();
    int seq[n];
    int index=1;
    if(left2right){
        seq[0]=arr.at(0);
        for(int i=1;i<n;i++){
            int height=arr.at(i);
            if(height>seq[index-1]){
                dp[i]=index+1;
                seq[index]=height;
                index++;
            }else{
                int l=0,r=index-1;
                while(l<r){
                    int mid=(l+r)/2;
                    if(seq[mid]<height){
                        l=mid+1;
                    }else{
                        r=mid;
                    }
                }
                seq[l]=height;
                dp[i]=l+1;
            }
        }
    }else{
        seq[0]=arr.at(n-1);
        for(int i=n-2;i>=0;i--){
            int height=arr.at(i);
            if(height>seq[index-1]){
                dp[i]=index+1;
                seq[index]=height;
                index++;
            }else{
                int l=0,r=index-1;
                while(l<r){
                    int mid=(l+r)/2;
                    if(seq[mid]<height){
                        l=mid+1;
                    }else{
                        r=mid;
                    }
                }
                seq[l]=height;
                dp[i]=l+1;
            }
        }
    }
}
int main(){
    std::vector<int> arr;//={186,186,150,200,160,130,197,200};
    int n=8;
    std::cin>>n;
    for(int i=0;i<n;i++){
        int h;
        std::cin>>h;
        arr.push_back(h);
    }
    int left_dp[n];
    int right_dp[n];
    for(int i=0;i<n;i++){
        left_dp[i]=0;
        right_dp[i]=0;
    }
    get_dp2(arr,left_dp);
    get_dp2(arr,right_dp,false);
    int mx=1;
    for(int i=0;i<n;i++){
        mx=max(mx,left_dp[i]+right_dp[i]-1);
    }
    std::cout<<n-mx<<std::endl;
}

 get_dp2中计算最长子序列，维护一个递增的数组seq，可以采用二分查找的方法，确定当前高度height=arr[i]在seq中的位置坐标，而l+1就是最长子序列长度。

seq[l]=height;
dp[i]=l+1;

 举例分析，186,186,150,200,160,130,197,200。第一趟，从左到右扫描。seq[0]=186，dp[0]=0

Reference:
[1] 笔试算法合唱队