题解 | #合唱队#

//两次递归，从左到右递归每一个节点的左侧最大值
//从右到左递归每一个节点的右侧最大值

#include <iostream>
#include<vector>

using namespace std;

int main() {
    int n;    
    while (cin >> n) { // 注意 while 处理多个 case
        int rdp[3001];//存储每个节点的左侧dp，这里r和l写反了，只能将错就错了
        int ldp[3001];//存储每个节点的右侧dp
        int a[3001];//储存身高信息
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
            rdp[i]=1;//初始化自身在队情况
            ldp[i]=1;
            for(int j=1;j<i;j++)//rdp，左侧递归求解每个节点作为中间节点时的左侧最大值
            {
                if((a[j]<a[i])&&(rdp[j]+1)>rdp[i])
                {
                    rdp[i]=rdp[j]+1;
                }
            }
        }
        for(int i=n;i>=1;i--)//ldp，类似上
        {
            for(int j=n;j>i;j--)
            {
                if((a[j]<a[i])&&(ldp[j]+1)>ldp[i])
                {
                    ldp[i]=ldp[j]+1;
                }
            }
        }
        int max=0;
	  //最终结果max为每个节点的左侧最大值（含自己作为中间）+右侧最大值（含自己作为中间）
	  //因为包含两次自己，所以最后结果max=max-1；
	  //答案输出n-max
        for(int i=1;i<=n;i++)
        {
            if(ldp[i]+rdp[i]-1>max)
            {
                max=ldp[i]+rdp[i]-1;
            }
        }

        cout<<n-max<<endl;
    }
}
// 64 位输出请用 printf("%lld")