题解 | #[NOIP2004]合唱队形#

从左边求一次最大上升子串，再从右边选一次，每一个人只有两个状态：选或者不选，每次维护后求解一段区间的最大值，符合动态规划思想，以下为代码

using namespace std;
int n;
int stu[500],l[500],r[500];
int main(){
    cin>>n;
    for(int i=1; i<=n; i++)
        cin>>stu[i];
    for(int i=1; i<=n; i++){
        l[i]=1;
    for(int x=1; x<=i; x++){
        if(stu[i]>stu[x])
            l[i]=max(l[i],l[x]+1);
        }
    }
    
    for(int i=n; i>=1; i--){
        r[i]=1;
    for(int x=n; x>=i; x--){
        if(stu[i]>stu[x])
           r[i]=max(r[i],r[x]+1);
        }
    }
    
    int maxn=0;
    for(int i=1; i<=n; i++)
        maxn=max(l[i]+r[i]-1,maxn);
    
    cout<<n-maxn;
    return 0;
}