合唱队形

题目 合唱队形

思路分析

先增后减序列 最少删除几个人

那其实问题可以转变成

达到最长子序列 还有多少人 然后把总人数减去这个最长子序列的长度即可

代码和上题一模一样了

在最后输出n-res即可

代码实现

#include<bits/stdc++.h>

using namespace std;

const int N=110;

int w[N];

int f_up[N],f_dw[N];

int n;

int main()

{

    cin>>n;

    for(int i=1;i<=n;i++)

        cin>>w[i];

    for(int i=1;i<=n;i++){

        f_up[i]=1;

        for(int j=1;j<i;j++){

            if(w[j]<w[i])

                f_up[i]=max(f_up[i],f_up[j]+1);

        }

    }

    for(int i=n;i>=1;i--){

        f_dw[i]=1;

        for(int j=n;j>i;j--){

            if(w[j]<w[i])

                f_dw[i]=max(f_dw[i],f_dw[j]+1);

        }

    }

    int res=0;

    for(int i=1;i<=n;i++){

        res=max(res,f_up[i]+f_dw[i]-1);

    }

    cout<<n-res<<endl;

    return 0;

}

同类题型

视频讲解

⬅️ 友好城市 🏠 00-刷题理模型 ➡️ 地宫取宝