ACM. Hj24 chorus ●●

HJ24 chorus ●●

describe

N Three students stand in a row , The music teacher should ask the least students to stand out , Make the rest K Three students form a chorus .

set up K The students are numbered from left to right 1,2…,K , Their heights are $T_k$, Can find a classmate , His Both sides Of the students are in order of height Strictly reduce The formation of is the chorus formation .

Example ：
123 124 125 123 121 It's a chorus formation
123 123 124 122 Not a chorus formation , Because the first two students are equal in height , Unqualified
123 122 121 122 Not a chorus formation , Because I can't find a classmate , His classmates on both sides are decreasing in height .

Your task is , All known N The height of a classmate , At least a few students are required for calculation , It can make the rest of the students form a chorus .

Be careful ： Changing the order of queue elements is not allowed And Does not require The number of top students must be equal

Data range ： $1\le n\le 3000$

Input description ：

Use case two lines of data , The first line is the total number of students N , The second line is N The height of a classmate , Space off

Output description ：

At least a few students are required to stand out

Example

Input ：
8
186 186 150 200 160 130 197 200
Output ：
4
explain ：
Since it is not allowed to change the order of queue elements , So the final remaining queue should be 186 200 160 130 or 150 200 160 130

Answer key

1. Dynamic programming （ The longest increasing subsequence ）

In order to get the minimum number of people out of the queue , So we can calculate that when we take a certain height as the midpoint , The maximum number of eligible people on both sides of him and , The final result is the total number of people minus the number of chorus lines .

therefore , We can use two arrays left、right, Record a certain height as the end point 、 The longest increment at the starting point / Decreasing subsequence sum .

such , Then the problem can be transformed into 300. The longest increasing subsequence ●● A similar situation .

• Time complexity ：$O(n^2)$, The array needs to be traversed multiple times , Two layers of for A nested loop .
• Spatial complexity ：$O(n)$, Save in every location dp Increment and decrement arrays .

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

int main(){
    
    int n;
    cin >> n;
    vector<int> statures(n, 0);
    for(int i = 0; i < n; ++i){
    
        cin >> statures[i];
    }
    vector<int> left(n, 0);
    vector<int> right(n, 0);
    for(int i = 0; i < n; ++i){
    
        for(int j = i-1; j >= 0; --j){
    
            if(statures[i] > statures[j]){
    
                left[i] = max(left[i], left[j] + 1);	// staturs[i] The longest increasing subsequence before 
            }
        }
    }
    for(int i = n-1; i >= 0; --i){
    
        for(int j = i+1; j < n; ++j){
    
            if(statures[i] > statures[j]){
    
                right[i] = max(right[i], right[j] + 1);	// staturs[i] The longest decreasing subsequence after 
            }
        }
    }
    int ans = 0;
    for(int i = 0; i < n; ++i){
    							//  Calculation and comparison results 
        ans = max(ans, (left[i]+right[i]+1) * (left[i]>0 && right[i]>0));
    }
    cout << n-ans;
    return 0;
}

2. Dynamic programming + Dichotomy

Use a dynamic array to record the current sequence , And use the dichotomy to insert and sort , Get the length of the longest subsequence , Specific view 300. The longest increasing subsequence ●●

• Time complexity ：$O(nlo{g}_2(n))$, With the help of dichotomy .
• Spatial complexity ：$O(n)$, An array of left and right subsequence values .

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

int main(){
    
    int n;
    cin >> n;
    vector<int> statures(n, 0);
    for(int i = 0; i < n; ++i){
    
        cin >> statures[i];
    }
    vector<int> left(n, 1);					// left Express staturs[i] The length of the longest increasing subsequence at the end 
    vector<int> dpl;
    dpl.emplace_back(statures[0]);			//  Dynamic programming array 
    for(int i = 1; i < n; ++i){
    
        if(statures[i] > dpl[dpl.size()-1]){
    
            dpl.emplace_back(statures[i]);
            left[i] = dpl.size();
            continue;
        }
        int l = 0, r = dpl.size()-1;
        while(l <= r){
    
            int mid = (l+r) >> 1;
            if(dpl[mid] >= statures[i]){
    
                r = mid - 1;
            }else{
    
                l = mid + 1;
            }
        }
        dpl[l] = statures[i];			//  Replace position 
        left[i] = l + 1;				//  Update here staturs[i] Corresponding subsequence length , namely l+1
    }
    vector<int> right(n, 1);			// right Express staturs[i] The longest decreasing subsequence length at the beginning 
    vector<int> dpr;
    dpr.emplace_back(statures[n-1]);	//  Dynamic programming array 
    for(int i = n-2; i >= 0; --i){
    
        if(statures[i] > dpr[dpr.size()-1]){
    
            dpr.emplace_back(statures[i]);
            right[i] = dpr.size();
            continue;
        }
        int l = 0, r = dpr.size()-1;
        while(l <= r){
    
            int mid = (l+r) >> 1;
            if(dpr[mid] >= statures[i]){
    
                r = mid - 1;
            }else{
    
                l = mid + 1;
            }
        }
        dpr[l] = statures[i];
        right[i] = l + 1;				//  Update here staturs[i] Corresponding subsequence length , namely l+1
    }
    int ans = 0;
    for(int i = 0; i < n; ++i){
    			//  The queue length and when all heights are midpoint 
        ans = max(ans, (left[i]+right[i]-1) * (left[i]>0 && right[i]>0));
    }
    cout << n-ans;						//  The number of people listed 
    return 0;
}