---
title: "合唱队形"
created: 2025-11-28
tags:
  - 算法
---

# 合唱队形

## 题目 [合唱队形](https://www.acwing.com/problem/content/description/484/)

![[image-c1b11168.png]]

## 思路分析

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

那其实问题可以转变成

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

代码和上题一模一样了

在最后输出n-res即可

## 代码实现

```cpp
#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-刷题理模型]] ➡️ [[地宫取宝|地宫取宝]]