题解 | #合唱队#动态规划 最长递增子序列的变体

#include <iostream>
#include <vector>
#include <string>
using namespace std;
/*等价于动态规划的经典问题，最长递增子序列。每一个元素，正着找他的最长递增子序列长度，再倒着找他的最长递增子序列长度，想加之后-1，就是最长梯度子序列长度，保证每一侧都是梯度递增的
1) d[i]以nums[i]结尾的子序列中最长递增子序列的个数为dp[i]
2)递推公式 每一个i,用j遍历0～i,如果num[j]<num[i]说明递增关系成立，对于这个j而言，最大子序列长度dp[i]=dp[j]+1  （因为j结尾的最大递增子序列，再加上元素i，所以长度+1）   此外要求最大的子序列长度，所以每出现一个更大的就会给dp[i]更新一次值，知道找到最大的，用MAX函数更新
即 dp[i]=max(dp[j]+1,dp[i])
3)初始化 需要知道比i小的j的dp[j]去得到dp[i].dp[0]=1，其他位最小都是1，可以用1初始化数组，再去覆盖更新
4）遍历顺序，由小到大，两层嵌套
以上正着做一遍，倒着做一遍，再相加-1，找到最终dp数组中的最大值，这是留下的同学数。N-这个最大值，=最少要出列的同学数
4*/
int main() {
    int N;
    cin>>N;
    int nums[N];
    for(int i=0;i<N;i++){
        cin>>nums[i];
    }
    vector<int>dp1(N,1);
    vector<int>dp2(N,1);
    vector<int>dp(N,0);
    int MAX_val=0;
    //正着求dp
    for(int i=1;i<N;i++){
        for(int j=0;j<i;j++){
            if(nums[j]<nums[i]){
            dp1[i]=max(dp1[j]+1,dp1[i]);}
        }
    }
    //倒着求dp,dp2[i]表示从nums[N-1]到nums[i]的子序列中最长递增子序列的长度,初始化dp[N-1]=1
    for(int i=N-2;i>=0;i--){
        for(int j=N-1;j>i;j--){
            if(nums[j]<nums[i]){
            dp2[i]=max(dp2[j]+1,dp2[i]);}
        }
    }
    for(int i=0;i<N;i++){
        dp[i]=dp1[i]+dp2[i]-1;
        if(dp[i]>MAX_val){MAX_val=dp[i];}
    }
    cout<<N-MAX_val<<endl;

    return 0;
}
// 64 位输出请用 printf("%lld")