题解 | #合唱队#

最长上升子序列的问题

分析提题意，可以得出，只要求出两侧的最长上升子序列，就可以得到删除数字最小的序列，其中注意求最长上升子序列的dp模板。

#include <vector>
using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<int> nums;
    while (n --)
    {
        int k;
        cin >> k;
        nums.push_back(k);
    }
    n = nums.size();
    vector<int> numL(n + 1, 1);
    vector<int> numR(n + 1, 1);
    //求最长上升子序列
    for (int i = 1; i <= n; i ++ )
    {
        for (int j = 0; j < i; j ++ )
            if (nums[i] > nums[j]) numL[i] = max(numL[i], numL[j] + 1);
    }
    
    for (int i = n - 1; i >= 0; i -- )
        for (int j = n - 1; j > i; j -- )
            if (nums[i] > nums[j]) numR[i] = max(numR[i], numR[j] + 1);
    
    int ans = 0;
    //找最长的子序列，再用n-最长的子序列就是需要去掉的人
    for (int i = 0; i < n; i ++ )
    {
        if (ans < (numL[i] + numR[i] - 1))
            ans = numL[i] + numR[i] - 1;
    }
    cout << n - ans << endl;
}