题解 | #合唱队#

合唱队

https://www.nowcoder.com/practice/6d9d69e3898f45169a441632b325c7b4

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(){
    int n, tmp;
    int i, j;
    vector<int> heights;
    // 输入
    while(cin >> n){
        for(i = 0; i < n; i++){
            cin >> tmp;
            heights.push_back(tmp);
        }
        // 设置两个dp数组
        vector<int> dp_h(n, 1), dp_t(n, 1);
        // 正序遍历
        for(i = 0; i < n; i++){
            for(j = 0; j < i; j++){
                if(heights[i] > heights[j]){
                    dp_h[i] = max(dp_h[i], dp_h[j] + 1);//比较{原始dp_h[i]的值,还是dp_h[j]结果加上选i这个位置},谁更大,更新到dp_h[i]中
                }
            }
        }
        // 逆序遍历
        for(i = n-1; i >= 0; i--){
            for(j = n-1; j > i; j--){
                if(heights[i] > heights[j]){
                    dp_t[i] = max(dp_t[i], dp_t[j] + 1);
                }
            }
        }
        // 求和得到最长先增后减子序列的长度
        int maxNum = 0;
        for(i = 0; i < n; i++){
            if(dp_t[i] + dp_h[i] - 1 > maxNum)
                maxNum = dp_t[i] + dp_h[i] - 1;
        }
        // 输出
        cout << n - maxNum << endl;
        // 清除vector,以供下一轮使用
        heights.clear();
    }
    return 0;
}

全部评论

相关推荐

双非一本失业第二年:《机器视觉垃圾分类》
点赞 评论 收藏
分享
尊嘟假嘟点击就送:加v细说,问题很大
点赞 评论 收藏
分享
评论
点赞
收藏
分享
牛客网
牛客企业服务