2128: 信息学奥赛一本通T1264-合唱队形 最长的双向递增子序列

解题思路:

注意事项:

参考代码:

#include"bits/stdc++.h"
using namespace std;
int main(){
    // 定义变量n表示数组长度，a数组存储输入数据，dp和dp2数组用于动态规划
    int n, a[105], dp[105], dp2[105];
    // 读取输入的数组长度
    cin >> n;
    // 读取数组元素并初始化dp和dp2数组
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        dp[i] = 1;
        dp2[i] = 1;
    }
    // 计算从左到右的最长递增子序列长度
    for(int i = 1; i <= n; i++){
        for(int j = 1; j < i; j++){
            if(a[i] > a[j]){
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
    }
    // 计算从右到左的最长递增子序列长度
    for(int i = n; i >= 1; i--){
        for(int j = i + 1; j <= n; j++){
            if(a[i] > a[j]){
                dp2[i] = max(dp2[i], dp2[j] + 1);
            }
        }
    }
    // 计算最长的双向递增子序列长度
    int kkk = -1;
    for(int i = 1; i <= n; i++){
        kkk = max(kkk, dp[i] + dp2[i] - 1);
    }
    // 输出结果：原数组长度减去最长双向递增子序列的长度
    cout << n - kkk << endl;
    return 0;
}