题解 | 合唱队

#include <iostream>
#include<vector>
using namespace std;
//遍历每一位同学作为中心位置，对中心的左边部分求LIS,对右边部分求最长递减子序列，将两部分长度相加求和，最后我们取所有和中的最大值即可
//LIS问题：1，状态定义：dp[i]表示以s[i]结尾的LIS长度 2，转移方程：dp[i]=max(dp[j])+1,有j<i,并且s[j]<s[i](可以将s[i]作为结尾添加到以s[j]结尾的LIS中) 3，边界条件：dp[i]=1(至少长度为一);
//LDS问题：和LIS问题的处理逻辑相同，dp[i]=max(dp[j])+1,有j<i,并且s[j]>s[i](可以将s[i]作为结尾添加到以s[j]结尾的LDS中)
int main() {
    int num;//同学数量
    cin>>num;
    vector<int>height(num,0);//记录同学的身高
    for(int i=0; i<num; i++)
        cin>>height[i];
    vector<int>LIS(num,1);//记录LIS长度
    vector<int>LDS(num,1);//记录LDS长度
   for(int i=1; i<num; i++)//遍历s[1]到s[num-1]
   {
        //遍历s[0]到s[i-1]求出左部分的LIS长度
        for(int j=0; j<i; j++)
        {
            if(height[j]<height[i])//求LIS
                LIS[i]=max(LIS[i],LIS[j]+1);
        }
   }
   for(int i=num-2; i>=0; i--)//遍历s[num-2]到s[0](求LIS的逆过程)
   {
        //遍历S[num-1]到s[i+1]求右部分的LDS长度（逆向的LIS长度）
        for(int j=num-1; j>i; j--)
        {
            if(height[j]<height[i])
                LDS[i]=max(LDS[i],LDS[j]+1);
        }
   }
    //求和的最大值
    int maxsum=0;//LIS和LDS长度之和的最大值
    for(int i=0; i<num; i++)
        maxsum=max(maxsum,LIS[i]+LDS[i]);
    //最后输出的是出列同学的数量不要搞错了
    cout<<num-maxsum+1;//重复计算了一位
    return 0;
}
// 64 位输出请用 printf("%lld")