题解 | #合唱队#

计算最少出列多少位同学，使得剩下的同学排成合唱队形
说明：
N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。
合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1，2…，K，他们的身高分别为T1，T2，…，TK， 则他们的身高满足存在i（1<=i<=K）使得T1<T2<......<Ti-1<ti>Ti+1>......>TK。
你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。
思路：动态规划
(1)：找[0, j]长度的数组中最长递增子序列(动态规划实现)
1.dp[i]:表示[0, i]内最长递增子序列长度
2.动态方程：如果nums[i] > nums[i-1],则dp[i] = max(dp[i], dp[i - 1] + 1)
3.初始化条件
dp[i] = 1
4.遍历顺序
从左往右</ti>

vector<int> increasingSequence(const vector<int>& nums){
    vector<int> dp(nums.size(), 1);
    for(int i = 1; i < dp.size(); ++i){
        for(int j = 0; j < i; ++j){
            if(nums[i] > nums[j])
                dp[i] = max(dp[i], dp[j] + 1);
        }
    }
    return dp;
}

(2)：找[j, nums.size() - 1]长度的数组中最长递减子序列(动态规划实现)
1.dp[i]:表示[i, nums.size() - 1]内最长递减子序列长度
2.动态方程：如果nums[i] > nums[i+1],则dp[i] = max(dp[i], dp[i + 1] + 1)
3.初始化条件
dp[i] = 1
4.遍历顺序
从右往左

vector<int> decreasingSequence(const vector<int>& nums){
    vector<int> dp(nums.size(), 1);
    int n = nums.size();
    for(int i = n - 2; i >= 0; --i){
        for(int j = n - 1; j > i; --j){
            if(nums[i] > nums[j])
                dp[i] = max(dp[i], dp[j] + 1);
        }
    }
    return dp;
}

最终实现代码

#include<iostream>
#include<vector>
using namespace std;
vector<int> increasingSequence(const vector<int>& nums);
vector<int> decreasingSequence(const vector<int>& nums);
int main(){
    int n;
    while(cin >> n){
        vector<int> high;
        int h;
        for(int i = 0; i < n; ++i){
            cin >> h;
            high.push_back(h);
        }
        vector<int> v1 = increasingSequence(high);
        vector<int> v2 = decreasingSequence(high);
        int maxLen = v1[0] + v2[0] - 1;
        for(int i = 1; i < v1.size(); ++i){
            if(v1[i] + v2[i] - 1 > maxLen)
                maxLen = v1[i] + v2[i] - 1;
        }
        cout << high.size() - maxLen << endl;
    }
    return 0;
}

vector<int> increasingSequence(const vector<int>& nums){
    vector<int> dp(nums.size(), 1);
    for(int i = 1; i < dp.size(); ++i){
        for(int j = 0; j < i; ++j){
            if(nums[i] > nums[j])
                dp[i] = max(dp[i], dp[j] + 1);
        }
    }
    return dp;
}

vector<int> decreasingSequence(const vector<int>& nums){
    vector<int> dp(nums.size(), 1);
    int n = nums.size();
    for(int i = n - 2; i >= 0; --i){
        for(int j = n - 1; j > i; --j){
            if(nums[i] > nums[j])
                dp[i] = max(dp[i], dp[j] + 1);
        }
    }
    return dp;
}