题解：P1091 [NOIP 2004 提高组] 合唱队形

FISH酱 · 2025-02-21 22:19:52 · 题解

前置知识

本篇题解主要讲解最长上升子序列的做法，如果你还不会，可以去做模板题。

解题思路

本题通过题面可知，我们希望一个队形里面的身高是先递增后递减的，那就可以分开求，最长递增的长度和最长递减的长度，最后枚举找最大值，即找出符合要求的最长队形的长度，用原队形长度减去符合要求的最长队形长度，就可以得到需要出列的同学个数。总结一下，我们需要求出最长上升子序列和最长下降子序列。

代码展示

写的时候注意细节即可，特别是求最长上升子序列和最长下降子序列时的实现，同时要注意审题，题目问的是出列人数，下面是代码：

#include <bits/stdc++.h>

using namespace std;

int n,ans=-1; // 定义变量
int a[1007]; // 定义身高数组
int dp1[1007]; // 最长上升子序列的dp数组
int dp2[1007]; // 最长下降子序列的dp数组

int main(){
    cin >> n; // 读入同学总数

    for(int i=1;i<=n;i++){
        cin >> a[i]; // 读入身高
    }

    // 求最长上升子序列长度
    for(int i=1;i<=n;i++){
        for(int j=0;j<i;j++){
            if(a[j]<a[i]){ // 如果满足递增要求就更新
                dp1[i] = max(dp1[i],dp1[j]+1); // 判断拼接转移后长度是否更长
            }
        }
    }

    // 求最长下降子序列长度，我们可以反着找
    for(int i=n;i>0;i--){
        for(int j=n+1;j>i;j--){
            if(a[j]<a[i]){
                dp2[i]=max(dp2[i],dp2[j]+1); // 判断拼接转移后长度是否更长
            }
        }

        for(int i=1;i<=n;i++){
            ans=max(dp1[i]+dp2[i]-1,ans); // 找符合要求的最长队形长度
        }
    }

    cout << n-ans; // 注意题目问的是出列人数

    return 0;
}