题解 | #合唱队#

#include <iostream>
using namespace std;

void maxDp(const int nums[], int dp[], const int n) {
    for (int i = 1; i < n ; i++) {
        for (int j = 0; j < i ; j++) {
            if (nums[i] > nums[j]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
    }
}

int main() {
    int n;
    cin >> n;
    int nums1[n];//正序排
    int nums2[n];//倒序排
    int dp1[n];//正dp
    int dp2[n];//倒dp
    //读数顺便初始化数组
    for (int i = 0; i < n; i++) {
        cin >> nums1[i];
        dp1[i] = 1;
        dp2[i] = 1;
        nums2[n - i - 1] = nums1[i];
    }

    maxDp(nums1, dp1, n);
    maxDp(nums2, dp2, n);

    int maxNum = 0;
    for (int i = 0; i < n ; i++) {
        if (maxNum < dp1[i] + dp2[n - i - 1] - 1 ) {
            maxNum = dp1[i] + dp2[n - i - 1] - 1;
        }
    }

    cout << n - maxNum << endl;

}

这题是最长子序列的衍生问题，只要把数组反过来再做一个dp数组，然后找2头加起来队列最大的那个就没毛病了。

附上最长子序列笔记。

2.1最长递增子序列

2.1.1问题描述：

• 在一个数组中选取某些元素，元素之间保持数组原有顺序并保持递增

2.1.2 dp[i]的含义

• 以num[i]为结尾的最长递增子序列的长度

2.1.3 递推公式

• if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);

2.1.4 dp数组的初始化

• dp[i] = 1;默认为自身

2.1.5 遍历顺序（2层for循环）

• i从1开始小到大遍历（dp[0] = 1）
• j从小到大或者从大到小都可以,默认从小到i就可以了

for (int i = 1; i < nums.size(); i++) {    for (int j = 0; j < i; j++) {        if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);    }    if (dp[i] > result) result = dp[i]; // 取长的子序列}

2.1.6 结果

• dp数组的最大值，可以在dp遍历的时候求即可