题解 | #合唱队#

思路

合唱队问题可以转换为求列表中最长升序子序列和最长降序子序列问题。求出来之后，n - 最长生序列的长度+最长降序列长度 - 1 的最小值，即使本题的解。

代码

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

using namespace std;

int main()
{
    int n, i;
    while( cin >> n )
    {
        vector<int> nums(n);
        for(i = 0; i < n; i++)
            cin >> nums[i];
        vector<int> dp(n), dp_de(n);
        for(i = 0; i < n; i++)
        {
            dp[i] = 1;
            for(int j = 0; j < i; j++)
            {
                if(nums[j] < nums[i] && (dp[j] + 1) > dp[i])
                    dp[i] = dp[j] + 1;
            }
        }
        
        for( i = n - 1; i >= 0; i--)
        {
            dp_de[i] = 1;
            for( int j = n-1; j > i; j-- )
            {
                if( nums[j] < nums[i] && (dp_de[j] + 1) > dp_de[i])
                    dp_de[i] = dp_de[j] + 1;
            }
        }
        
        int minNum = n;
        for( i = 0; i < n; i++ )
        {
            minNum = min(minNum, n-(dp[i] + dp_de[i] - 1));
        }
        cout << minNum << endl;
    }
    return 0;
}