首页 > 试题广场 >

合唱队形

[编程题]合唱队形

热度指数：3737 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

N位同学站成一排，音乐老师要请其中的 (N-K) 位同学出列，使得剩下的K位同学排成合唱队形。

合唱队形是指这样的一种队形：设K位同学从左到右依次编号为 1，2…，K，他们的身高分别为 T₁，T₂，…，T_K，则他们的身高满足 $t_1 < t_2 ... < t_i > t_{i+1} > ... > t_{k-1} > t_k (1 \le i \le k) \$

你的任务是，已知所有 n 位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。

数据范围： $1 \le n \le 1000 \$ ，身高满足 $130 \le t_i \le 230 \$

输入描述:

第一行输入一个正整数 n 表示同学的总数。
第二行有 n 个整数，用空格分隔，第 i 个整数 t_i是第 i 位同学的身高(厘米)。

输出描述:

输出仅有一个整数，即最少需要几个同学出列

示例1

输入

8
186 186 150 200 160 130 197 220

输出

算法知识视频讲解

C++

Spectre_

#include <iostream>
using namespace std;

int main() {
    int n, res = 0;
    cin >> n;
    int arr[n], dp1[n], dp2[n];
    // 时间复杂度O(N^2)，空间复杂度O(N)
    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
        dp1[i] = 1;
        dp2[i] = 1;
    }
    // 从左往右，最长上升子序列长度
    for (int i = 1; i < n; ++i)
        for (int j = 0; j < i; ++j)
            if (arr[j] < arr[i]) dp1[i] = max(dp1[j] + 1, dp1[i]);
    // 从右往左，最长上升子序列长度
    for (int i = n - 2; i >= 0; --i) 
        for (int j = n - 1; j > i; --j) 
            if (arr[i] > arr[j]) dp2[i] = max(dp2[j] + 1, dp2[i]);
    // i位置处，左边最长上升子序列长度 + 右边最长上升子序列长度 - 1（i位置多算了一次）
    for (int i = 0; i < n; ++i) res = max(res, dp1[i] + dp2[i] - 1);
    cout << n - res;
    return 0;
}

发表于 2022-11-01 16:55:06 回复(0)

牛客212561046号

#include <iostream>
#include <vector>
using namespace std;

int main() {

    int n;
    cin>>n;
    vector<int> arr(n);
    for(int i=0; i<n; i++){
        cin>>arr[i];
    }
    vector<int> dp1(n,1); //dp1[i]以i为结尾的最长递增子序列长度
    vector<int> dp2(n,1); //dp2[i]以i为开头的最长递减子序列长度
    for(int i=1; i<n; i++){
        for(int j=0; j<i; j++){
            if(arr[i]>arr[j]){
                dp1[i] = max(dp1[i],dp1[j]+1);
            }
        }
    }

    for(int i=n-2; i>=0; i--){
        for(int j=n-1; j>i; j--){
            if(arr[i]>arr[j]){
                dp2[i] = max(dp2[i],dp2[j]+1);
            }
        }
    }

    int res=1;
    for(int k=0; k<n; k++){
        res = max(res, dp1[k]+dp2[k]-1);
    }
    cout<<n-res;
    return 0;
}

编辑于 2023-12-29 18:50:12 回复(0)

昊天明月

也就是左侧以i为结尾的最长递增子序列长度，和以i为开始，最长递减子序列长度。要求两者和的最大值。

发表于 2023-07-05 15:48:32 回复(0)

Python3

枺翳

while True:
    try:
        n = int(input())
        s = list(map(int, input().split()))

        dpin = [1]*n
        dpin_re = [1]*n
        save = []

        #以s[i]结尾，正序最长增子列
        for i in range(1, n):
            for j in range(i):
                if s[i] > s[j]:
                    dpin[i] = max(dpin[i], dpin[j]+1)
        #以s[i]结尾，反序最长增子列 = 以s[i]开头，正序最长减子列
        for i in range(n-1, -1, -1):
            for k in range(n-1, i, -1):
                if s[i] > s[k]:
                    dpin_re[i] = max(dpin_re[i], dpin_re[k]+1)
        
        for i in range(n):
            save.append(dpin[i]+dpin_re[i]-1) #s[i]在两个最长子列中被算2次，需减去1次
    
        print(len(s)-max(save))


    except:
        break

发表于 2022-09-20 00:40:17 回复(0)

Java

hh求offer

import java.util.Scanner;

public class Main{
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = Integer.parseInt(scanner.nextLine());
        String[] splits = scanner.nextLine().split(" +");
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = Integer.parseInt(splits[i]);
        }
        //从左往右 最长递增子序列
        int[] dp = new int[n];
        dp[0] = 1;
        for (int i = 1; i < n; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                if(nums[i] > nums[j]){
                    dp[i] = Math.max(dp[i],dp[j] + 1);
                }
            }
        }
        //从右往左 最长递增子序列
        int[] dp2 = new int[n];
        int ans = Integer.MAX_VALUE;
        for (int i = n-1; i >= 0; i--) {
            dp2[i] = 1;
            for (int j = n-1; j > i; j--) {
                if(nums[i] > nums[j]){
                    dp2[i] = Math.max(dp2[i], dp2[j]+1);
                }
            }
            // 每个位置需要出列的最少人数
            int tmp = n - dp[i] - dp2[i] + 1;
            ans = Math.min(ans,tmp);
        }
        System.out.println(ans);
    }
}

发表于 2022-05-05 11:15:10 回复(0)

C++

元气少女李逵

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
    int n;
    cin>>n;
    int b;
    vector<int> a;
    for(int i=0;i<n;i++)
    {
        cin>>b;
        a.push_back(b);
    }
    int temp=10000;
    for(int i=0;i<n;i++)
    {
        vector<int> p(n+1,1);
        vector<int> q(n+1,1);
        int temp1=1;
        int temp2=1;
        //0~i
        for(int j=i;j>=0;j--)
        {
            for(int l=j-1;l>=0;l--)
            {
                if(a[l]<a[j])
                {
                    p[l]=max(p[l],p[j]+1);
                }   
            }
            temp1=max(temp1,p[j]);
        }
        //i~n
        for(int h=i;h<n;h++)
        {
            for(int s=h+1;s<n;s++)
            {
                if(a[s]<a[h])
                {
                    q[s]=max(q[s],q[h]+1);
                }              
            }
            temp2=max(temp2,q[h]);
        }
        //每次都要计算n-temp1-temp2+1保证temp1和temp2在同一轮
        temp=min(temp,n-temp1-temp2+1);
    }
    cout<<temp<<endl;
    return 0;
}

发表于 2022-04-11 15:22:28 回复(0)