题解 | #合唱队#

#include <iostream>
#include <vector>
using namespace std;
// 要求一侧递增另一侧递减，可以通过双数组分别计算两侧的策略来简化问题
int main()
{
    int num;
    cin >> num;
    vector<int>heights(num,0);
    for(int i = 0;i<num;i++)
    {
        cin >> heights[i];
    }
    vector<int>dp_l(num,1);
    vector<int>dp_r(num,1);
    for(int i = 1;i<num;i++)
    {
        for(int j = 0;j<i;j++)
        {
            if(heights[i] > heights[j])
            {
                dp_l[i] = max(dp_l[j] + 1,dp_l[i]);
            }
            if(heights[num-1 - i] > heights[num - 1 - j])
            {
                dp_r[num-1 - i] = max(dp_r[num - 1 - i],dp_r[num-1 - j]+1);
            }
        }
    }
    int maxdlete = num;
    for(int i = 0;i<num;i++)
    {
        if(dp_l[i]+dp_r[i] - 1 > num - maxdlete)
        {
            maxdlete = num - (dp_l[i]+dp_r[i] - 1);
        }
    }
    cout << maxdlete << endl;


}
// 64 位输出请用 printf("%lld")