题解 | #合唱队#

找到去除最少的人，也就是保留最多的人。该问题可以转化成为找某个位置的最长递增子序列和递减子序列问题。也就是之前做过的走桩子问题。可以使用动态规划来解决。

找最长递增子序列长度，可以使用动态规划设置dp数组记录各位置长度，从左往右依次遍历各位置i，对于i，找位于i之前位置中个子低于i的j，如果j记录的最长子序列大于i的长度，那么更新dp[i]为dp[j]+1。

同理，对于递减子序列，相当于反向递增子序列，从后往前依次遍历。使用dp2记录

最后每个位置最长子序列长度相当于dp1+dp2-1,减1是因为长度多记录了一次。

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



int main() {
    int num = 0;
    cin >> num;

    vector<int> store(num);
    for(int i = 0; i < num; i++) cin>>store[i];


    vector<int> dp1(num,0), dp2(num,0);

    // 从前往后，找每个同学的前向最长递减子序列
    for(int i = 0; i < num; i ++){
        dp1[i] = 1;
        for(int j = 0; j < i; j ++){
            if(store[i]>store[j]){
                dp1[i] = dp1[i]>dp1[j]+1?dp1[i]:dp1[j]+1;
            }
        }
    }

    // 从后往前，找每个同学的后向最长递减子序列
    for(int i = num-1; i >= 0; i --){
        dp2[i] = 1;
        for(int j = i+1; j < num; j ++){
            if(store[i]>store[j]){
                dp2[i] = dp2[i]>dp2[j]+1?dp2[i]:dp2[j]+1;
            }
        }
    }

    // 找到最大的同学使两子序列加和最大
    int max_len = 0;
    for(int i = 0; i < num; i++)
        max_len = max_len>dp1[i]+dp2[i]-1? max_len:dp1[i]+dp2[i]-1;
    
    cout << num-max_len << endl;
}
// 64 位输出请用 printf("%lld")