首页 > 试题广场 >

合唱队

[编程题]合唱队
  • 热度指数：318091 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解

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

设K位同学从左到右依次编号为 1，2…，K ，他们的身高分别为 ，若存在 使得 且 ，则称这K名同学排成了合唱队形。
通俗来说，能找到一个同学，他的两边的同学身高都依次严格降低的队形就是合唱队形。
例子：
123 124 125 123 121 是一个合唱队形
123 123 124 122不是合唱队形，因为前两名同学身高相等，不符合要求
123 122 121 122不是合唱队形，因为找不到一个同学，他的两侧同学身高递减。


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

注意：不允许改变队列元素的先后顺序 且 不要求最高同学左右人数必须相等



输入描述:
用例两行数据，第一行是同学的总数 N ，第二行是 N 位同学的身高 h[i]，以空格隔开
  数据范围： ，0<=h[i]<=1e5


输出描述:
最少需要几位同学出列
示例1

输入

8
186 186 150 200 160 130 197 200

输出

4

说明

由于不允许改变队列元素的先后顺序，所以最终剩下的队列应该为186 200 160 130或150 200 160 130
算法知识视频讲解
添加回答
Java
牛客201673936号头像 牛客201673936号 
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) { 
            int N = in.nextInt();
            int[] T = new int[N];
            int[] left = new int[N];//记录从左往右的最长子序列数据
            int[] right = new int[N];//记录从右往左的最长子序列数据
            for (int i = 0; i < N; i++) {
                T[i] = in.nextInt();
            }

            //遍历找出左右最长序列数据,
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < i; j++) {
                    int m = N-1-i;
                    int n = N-1-j;
                    if(left[j] == 0){
                        left[j] = 1;
                    }
                    if(right[n] == 0){
                        right[n] = 1;
                    }
                    if(T[i]>T[j]){
                        left[i] = Math.max(left[i],left[j]+1);
                    }
                    if(T[m]>T[n]){
                        right[m] = Math.max(right[m],right[n]+1);
                    }
                }
            }
            int max = 0;
            //把每一个点作为最后一个请出同学，遍历比较得出最多剩下的同学
            for (int i = 0; i < N; i++){
                if(max < left[i]+right[i]-1){
                    //两者相加，减去重复计算的1，即为将此数放中间组成合唱队所需要的人数，取最大值max
                    max = left[i]+right[i]-1;
                }
            }
            System.out.println(N-max);
        }
    }
}

发表于 2024-09-06 13:00:19 回复(0)
Java
sinjiang头像 sinjiang
  • 常见的最长上升子序列问题

  • 思路： 1、查找每一个数的左边的最大递增子字符串长度，放入数组dp1中。 2、查找每个数的右边最大递增子字符串长度，放入数组dp2中 3、两者相加，减去重复计算的1，即为将此数放中间组成合唱队所需要的人数，取最大值max 4、总人数减去第三步所得，就可以得出需要出列的最少人数 注意：身高是递增的，不能等于 


import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) { 
            int N = in.nextInt();
            int[] T = new int[N];
            int[] left = new int[N];//记录从左往右的最长子序列数据
            int[] right = new int[N];//记录从右往左的最长子序列数据
            for (int i = 0; i < N; i++) {
                T[i] = in.nextInt();
            }

            //先从左往右找出最长子序列
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < i; j++) {
                    if(T[i]>T[j]){
                        left[i] = Math.max(left[i],left[j]);
                    }
                }
                left[i] = left[i]+1;
            }
            //再从右往左找出最长子序列
            for (int i = N-1; i >= 0; i--) {
                for (int j = N-1; j > i; j--) {
                    if(T[i]>T[j]){
                        right[i] = Math.max(right[i],right[j]);
                    }
                }
                right[i] = right[i] +1;
            }
            int max = 0;
            //把每一个点作为最后一个请出同学，遍历比较得出最多剩下的同学
            for (int i = 0; i < N; i++){
                if(max < left[i]+right[i]-1){
                    //两者相加，减去重复计算的1，即为将此数放中间组成合唱队所需要的人数，取最大值max
                    max = left[i]+right[i]-1;
                }
            }
            System.out.println(N-max);
        }
    }
}
发表于 2024-06-01 03:36:09 回复(0)
Java
早睡亿点头像 早睡亿点

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息

public class Main { 

private static int minTest(int[] heights){

    int n = heights.length;

    int[] ldp = new int[n];

    int[] rdp = new int[n];

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

        ldp[i] = 1;

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

            if(heights[i]>heights[j]){

                ldp[i] = Math.max(ldp[i],ldp[j]+1);

            }

        }

    }

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

        rdp[i] = 1;

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

            if(heights[i]>heights[j]){

                rdp[i] = Math.max(rdp[i],rdp[j]+1);

            }

        }

    }

    // 找到一个同学使得左侧和右侧最长递增子序列长度之和最大

    int res = 0;

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

        res = Math.max(res,rdp[i]+ldp[i]-1);

    }

    return n-res;

}

public static void main(String[] args) {

    Scanner sc = new Scanner(System.in);

    int n = sc.nextInt();

    int[] heights = new int[n];

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

        heights[i] = sc.nextInt();

    }

    int res = minTest(heights);

    System.out.println(res);

}

}

编辑于 2024-04-07 16:13:19 回复(0)
Java
//201910101754657头像 //201910101754657 
import java.util.Scanner;
import java.util.Arrays;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        sc.nextLine();
        String input = sc.nextLine();
        String[] arr = input.split(" ");
        int[] src = Arrays.stream(arr).mapToInt(Integer::parseInt).toArray();
        // 求left
        int[] left = new int[arr.length];
        for (int i = 0; i < src.length; i++) {
            left[i] = 0;
            for (int j = 0; j < i; j++) {
                if (src[j] < src[i]) {
                    left[i] = Math.max(left[i], left[j] + 1);
                }
            }
        }
        // 求right
        int[] right = new int[arr.length];
        for (int i = src.length - 1; i >= 0; i--) {
            right[i] = 0;
            for (int j = src.length - 1; j > i; j--) {
                if (src[j] < src[i]) {
                    right[i] = Math.max(right[i], right[j] + 1);
                }
            }
        }
        // 汇总
        int[] res = new int[src.length];
        for (int i = 0; i < res.length; i++) {
            res[i] = left[i] + right[i] + 1;
        }
        int result = arr.length - Arrays.stream(res).max().orElse(0);
        System.out.println(result);
    }
}

编辑于 2024-03-17 23:53:58 回复(0)
Java
axby头像 axby

最长上升子序列 + 最长下降子序列， 二分

import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; ++i) {
            a[i] = in.nextInt();
        }
        int mx = 0;
        for (int i = 0; i < n; ++i) {
            // 选 第 i 位 不出列 求左右两边严格最长上升和递减子序列长度
            // 结果为 两边长度之和加上中间这位的最大值， n - mx 就是要出列的人数
            int up = maxUp(a, 0, i - 1);
            int dn = maxDn(a, i + 1, n - 1);
            int s = up + dn + 1;
            if (s > mx) {
                mx = s;
            }
        }
        System.out.println(n - mx);
    }
    static int maxUp(int[] a, int l, int r) {
        if (l > r){
            return 0;
        }
        int[] dp = new int[r - l + 1];
        int len = r - l + 1;
        int pos = 0;
        for (int i = l; i <= r; ++i) {
            if (pos == 0 || a[i] > dp[pos - 1]) {
                dp[pos ++] = a[i];
            } else {
                int p = bs1(dp, 0, pos - 1, a[i]);

                dp[p + 1] = a[i];
            }
        }
        return pos - 1;
    }
    static int bs1(int[] a, int l, int r, int x) {
        int p = -1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (a[mid] < x) {
                p = mid;
                l = mid + 1;
            } else r = mid - 1;
        }
        return p;
    }
    static int maxDn(int[] a, int l, int r) {
        if (l > r){
            return 0;
        }
        int[] dp = new int[r - l + 1];
        int len = r - l + 1;
        int pos = 0;
        for (int i = l; i <= r; ++i) {
            if (pos == 0 || a[i] < dp[pos - 1]) {
                dp[pos ++] = a[i];
            } else {
                int p = bs2(dp, 0, pos - 1, a[i]);
                dp[p + 1] = a[i];
            }
        }
        return pos;
    }
    static int bs2(int[] dp, int l, int r, int x){
        int p = -1;
        while (l <= r){
            int mid = (l + r) / 2;
            if (dp[mid] > x){
                l = mid + 1;
                p = mid;
            }else r = mid - 1;
        }
        return p;
    }
}
编辑于 2024-03-15 17:58:41 回复(0)
Java
牛客214364484号头像 牛客214364484号 
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextLine()) {
            int n = sc.nextInt();
            sc.nextLine();  //防止回车符号 "/n 被计入下一个输入中,只有while(sc.hasNextLine())时候需要注意这里,
                            //其他的sc.hasNext()或者sc.hasNextInt()都不用在这里写这一行
            int[] a = new int[n];
            for (int i = 0; i < n; i++) {
                a[i] = sc.nextInt();
            }
            sc.nextLine();  //防止回车符号 "/n 被计入下一个输入中

            //左边最长递增子序列
            int[] dp1 = new int[n];
            for (int i = 0; i < n; i++) {
                dp1[i] = 1;     //全元素赋值为1
                for (int j = 0; j < i; j++) {
                    if (a[j] < a[i]) {
                        dp1[i] = Math.max(dp1[j] + 1, dp1[i]);//此处dp1[j] + 1中的+1指的是i位置元素          选↓        不选↓
              //同理01背包问题，当发现左侧有比a[i]小的元素时，我们可以选该元素作子序列元素，也可以不选。Math.max(dp1[j] + 1, dp1[i])
                    }
                }
            }

            //右边最长递减子序列
            int[] dp2 = new int[n];
            for (int i = n - 1; i >= 0; i--) {//右边要找递减子序列，所以注意倒序
                dp2[i] = 1;
                for (int j = n - 1; j > i; j--) {
                    if (a[j] < a[i]) {
                        dp2[i] = Math.max(dp2[j] + 1, dp2[i]);
                    }
                }
            }
            int res = 1;
            for (int i = 0; i < n; i++) { //计算每个预设位置i的最长子序列 = 左 + 右 - 1
                a[i] = dp1[i] + dp2[i] - 1;
                if (a[i] > res) {
                    res = a[i];
                }
            }
            System.out.println(n - res); //总人数减去最长子序列元素个数，也就是组成合唱团的人数，就得到了需要出列的人数 
        }
        sc.close();
    }
}

发表于 2024-01-23 18:00:18 回复(0)
Java
今生能进大厂吗头像 今生能进大厂吗 
最一开始没想到是动态规划,直接做的时候发现跟想的不一样,直接去评论区发现是动态规划问题

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int num = in.nextInt();
            int[] arr = new int[num];
            for (int i = 0; i < num ; i++) {
                arr[i] =  in.nextInt();
            }
            //左到右升序
            int[] left = new int[num];
            for (int i = 0; i < num ; i++) {
                left[i] = 1;//当前位置的数已经计数了 计数1
                for (int j = 0; j < i ; j++) {
                    //内循环在当前位置以内  注:arr [i]为当前索引数据, arr[j] 是arr [i]左边的数据
                    if (arr[j] < arr [i]) {
                        left[i] = Math.max(left[j] + 1, left[i]);
                    }
                }
            }
            //右到左升序
            int[] right = new int[num];
            for (int i = num - 1 ; i >= 0 ; i--) {
                right[i] = 1;//当前位置的数已经计数了 计数1
                for (int j = num - 1; j > i ; j--) {
                    //内循环在当前位置以内  注:arr [i]为当前索引数据, arr[j] 是arr [i]右边的数据
                    if (arr[j] < arr [i]) {
                        right[i] = Math.max(right[j] + 1, right[i]);
                    }
                }
            }
            int max = 0;
            for(int i= 0;i< num; i++){
                max = Math.max(left[i] + right[i] -1,max);// left[i] = 1; right[i] = 1; 导致当前索引的那个人多计数一次
            }

            System.out.println(num - max);
        }
    }
}

编辑于 2023-12-11 18:15:34 回复(0)
Java
不要香菜的潜伏者很想和你交朋友头像 不要香菜的潜伏者很想和你交朋友
这个答案错了，正确答案是112
发表于 2023-10-24 14:12:27 回复(1)
Java
在泡池子的小饼干很想被叫靓仔头像 在泡池子的小饼干很想被叫靓仔 
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int length = in.nextInt();
            int[] arr = new int[length];

            for (int i = 0; i < length; i++) {
                arr[i] = in.nextInt();
            }

            int[] left = new
            int[length]; // 每个节点向左递减最大的子序列长度
            int[] right = new
            int[length];// 每个节点向右递减最大的子序列长度

            // 初始化两个数列，全设置为1
            for (int i = 0; i < length; i++) {
                left[i] = 1;
                right[i] = 1;
            }

            for (int i = 0; i < length; i++) {
                for (int j = 0; j < i; j++) {
                    if (arr[i] > arr[j]) {
                        left[i] = Math.max(left[i], left[j] + 1);
                    }
                }
            }

            for (int i = length - 1; i > -1; i--) {
                for (int j = i + 1; j < length; j++) {
                    if (arr[i] > arr[j]) {
                        right[i] = Math.max(right[i], right[j] + 1);
                    }
                }
            }

            int maxNum = 0;
            int[] tempArr = new int[length];
            for (int i = 0; i < length; i++) {
                tempArr[i] = left[i] + right[i] - 1;
                maxNum = Math.max(tempArr[i], maxNum);
            }
            System.out.println(length - maxNum);

        }
        in.close();
        ;
    }
}

发表于 2023-07-03 19:47:59 回复(0)
Java
breeze_freedom头像 breeze_freedom
有大佬知道这个是怎么错的吗，数据量小的测试案例能通过 

package com.xlr.nowcoder;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

/**
 * 该题型是一个典型的动态规划+贪心
 * @see <a href="https://www.nowcoder.com/practice/6d9d69e3898f45169a441632b325c7b4?tpId=37&tqId=21247&rp=1&ru=/exam/oj/ta&qru=/exam/oj/ta&sourceUrl=%2Fexam%2Foj%2Fta%3FtpId%3D37&difficulty=undefined&judgeStatus=undefined&tags=&title=">HJ24 合唱队</a>
 */
public class HJ24 {
    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        while (scanner.hasNext()){
            int N=scanner.nextInt();
            ArrayList<Integer> list=new ArrayList<>();
            while (N-->0) list.add(scanner.nextInt());
            List<Integer> order =getIncrease(list);//顺着寻找最长递增子序列
            Collections.reverse(list);//将数组逆序
            List<Integer> reversed=getIncrease(list);//寻找逆序的最长递增子序列
            Collections.reverse(reversed);
            int max=-1;
            for(int index=0;index<order.size();index++){//找到顺序和逆序子序列之和，
                max=Math.max(max,order.get(index)+reversed.get(index));
            }
            System.out.println(list.size()-max+1);//因为当前元素多算了一遍故减去1个
        }
    }
    //计算最短增序列
    public static List<Integer> getIncrease(List<Integer> list){
        List<Integer > cnt=new ArrayList<>();//记录每个元素位置的最长递增子序列
        //计算每个元素的最长子串
        for(int index=0;index<list.size();index++){
            if(index<=0){//当前为第一个数字，直接加入最长递增子序列长度为1
                cnt.add(1);
            }else{
                int n=index;
                while (--n>=0){
                    if(list.get(n)<list.get(index)){//寻找前面最后一个比当前元素小的元素
                        break;
                    }
                }
                if(n>=0){//当n>=0存在时，找前面最后一个比当前元素小的元素,将该元素的最长递增子序列和当前元素组合并与上个元素比较最长的便是当前元素最长递增子序列
                    cnt.add(Math.max(cnt.get(index-1),cnt.get(n)+1));
                }else{
                    cnt.add(cnt.get(cnt.size()-1));//前面没有比当前元素小的元素，当前元素最长递增子序列就是上个元素的最长递增子序列
                }
            }
        }
        return cnt;
    }
}


发表于 2023-06-10 22:00:52 回复(1)
Java
牛客781396821号头像 牛客781396821号
动态规划，思路是找出每个人的左右侧各能有多少人，取左右侧之和最大的值
规律是左侧人数为 之前所有身高比当前身高低的人中 左侧人数最大的数值+1；右侧也是一样
注意陷阱（可能没有题目中的陷阱）：左右两侧任何一侧为1的数值不能使用，因为他不满足两侧都有比他低 
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int n = in.nextInt();
            int[] tall = new int[n];
            int[] left = new int[n];
            int[] right = new int[n];
            tall[0] = in.nextInt();
            left[0] = 1;
            right[n - 1] = 1;

            // 计算每个人的左侧加上自己能有多少人
            for (int i = 1 ; i < n ; i++) {
                tall[i] = in.nextInt();
                left[i] = 1;
                for (int j = i - 1 ; j >= 0 ; j--) {
                    if (tall[i] > tall[j]) {
                        left[i] = left[i] > (left[j] + 1) ? left[i] : left[j] + 1;
                    }
                }
            }

            // 计算每个人的右侧加上自己能有多少人
            for (int i = n - 2 ; i >= 0 ; i--) {
                right[i] = 1;
                for (int j = i + 1 ; j < n ; j++) {
                    if (tall[i] > tall[j]) {
                        right[i] = right[i] > (right[j] + 1) ? right[i] : right[j] + 1;
                    }
                }
            }

            // 找出左右侧之和的最大值
            int sum = left[0] + right[0];
            for (int i = 1 ; i < n ; i++) {
                if (left[i] == 1 || right[i] == 1) {
                    continue;
                }
                int sum1 = left[i] + right[i];
                sum = sum < sum1 ? sum1 : sum;
            }
            System.out.println(n - sum + 1);
        }
    }
}


发表于 2023-05-11 10:23:37 回复(0)
Java
303300589头像 303300589 
package HW;

import java.util.Scanner;

public class HJ24 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int n = in.nextInt();
            int[] ints = new int[n];
            for (int i = 0; i < n; i++) {
                ints[i] = in.nextInt();
            }
            int max = Integer.MAX_VALUE;
            // dp缓存
            int[][] dp = new int[n][n];
            for (int i = 0; i < n; i++) {
                // 以i为中心，检查左右
                int leftRes = checkLeft(i, i - 1, ints, dp);
                int rightRes = checkRight(i, i + 1, ints, dp);
                if (max > leftRes + rightRes) {
                    max = leftRes + rightRes;
                }
            }
            System.out.println(max);
        }
    }

    private static int checkRight(int cur, int right, int[] ints, int[][] dp) {
        if (cur >= ints.length || right >= ints.length) return 0;
        if (dp[cur][right]!=0)return dp[cur][right];
        // 比cur大，则必须出列
        if (right < ints.length && ints[right] >= ints[cur]) {
            int res = 1 + checkRight(cur, right + 1, ints,dp);
            dp[cur][right] = res;
            return res;
        } else {
            // 比cur小，不一定不出列
            // 尝试出列， 可能有这种情况：5，2，4，3，则2出列比不出列好
            int out = 1 + checkRight(cur, right + 1, ints,dp);
            // 尝试不出列
            int noOut = checkRight(right, right + 1, ints,dp);
            int res = Math.min(out, noOut);
            dp[cur][right] = res;
            return res;
        }
    }
    
    private static int checkLeft(int cur, int left, int[] ints, int[][] dp) {
        if (left < 0 || cur < 0) return 0;
        if(dp[cur][left]!=0) return dp[cur][left];
        if (left >= 0 && ints[left] >= ints[cur]) {
            int res = 1 + checkLeft(cur, left - 1, ints,dp);
            dp[cur][left] = res;
            return res;
        } else {
            // 比cur小，不一定不出列
            // 尝试出列， 可能有这种情况，3，4，2，5，则2出列比不出列好
            int out = 1 + checkLeft(cur, left - 1, ints, dp);
            // 尝试不出列
            int noOut = checkLeft(left, left - 1, ints, dp);
            int res = Math.min(out, noOut);
            dp[cur][left] = res;
            return res;
        }
    }
}

发表于 2023-04-02 19:36:44 回复(0)
Java
璃吻头像 璃吻
思路：以示例为准 
186 186 150 200 160 130 197 200
左                                                                          右
0：1->186                                                             3->186 150/160 130
1：1->186                                                             3->186 150/160 130
2：1->150                                                             2->150 130
3：2->186/150 200                                               3->200 160 130
4：2->150 160                                                      2->160 130
5：1->130                                                             1->130
6：3->150 160 197                                               1->197
7：4->150 160 197 200                                        1->200
先遍历数组获得左排序个数，再获得右排序个数，左+右-1即为合唱队人数，取最大值                  
0：3->186 150/160 130
1：3->186 150/160 130
2：2->150 130
3：4->186/150 200 160 130
4：3->150 160 130
5：1->130
6：3->150 160 197
7：4->150 160 197 200 

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextInt()) {
            int n = sc.nextInt();
            int[] a = new int[n];
            for (int i = 0; i < n; i++) {
                a[i] = sc.nextInt();
            }
            //left，遍历从左到i的升序个数
            int[] left = new int[n];
            for (int i = 0; i < n; i++) {
                left[i] = 1;//最起码当前数为1
                for (int j = 0; j < i; j++) {
                    if (a[j] < a[i]) {
                        //每有一个比a[i]小的数，在left[j]的基础上加1和left[i]比大小，保证是升序数
                        left[i] = Math.max(left[j] + 1, left[i]);
                    }
                }
            }
            //right，遍历从右到i的升序个数
            int[] right = new int[n];
            for (int i = n - 1; i >= 0; i--) {
                right[i] = 1;
                for (int j = n - 1; j > i; j--) {
                    if (a[j] < a[i]) {
                        right[i] = Math.max(right[j] + 1, right[i]);
                    }
                }
            }
            int people = 1;//1<=n<=3000，所以最少为合唱队最少1个人
            for (int i = 0; i < n; i++) {
                //以当前数为中心，左右升序数相加减一即是合唱队,重合了最高的人所以减一
                //直接使用a[i]数组，创建新数组浪费空间
                a[i] = left[i] + right[i] - 1;
                people = Math.max(people, a[i]); //取合唱队最大值
            }
            System.out.println(n - people); //总人数减去最大合唱队人数就是要出列的同学人数
        }

    }
}


发表于 2023-03-03 20:09:40 回复(0)
Java
董乃士头像 董乃士 
import java.util.Arrays;
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        // int nums[]={1,4,3,4,2,1,5,3};
        int nums[]=new int[n];
        for(int i=0;i<n;i++){
            nums[i]=sc.nextInt();
        }
        int[] dp1 = maxIncr(nums);
        int[] dp2 = maxDecr(nums);
        // System.out.println(Arrays.toString(dp1));
        // System.out.println(Arrays.toString(dp2));
        int[] dp3=new int[nums.length];
        int max=0;
        for(int i=0; i<nums.length; i++){
            dp3[i] =dp1[i]+dp2[i]-1;//最长 +最短-自己重复的一次
            max=Math.max(max,dp3[i]);
        }
        System.out.println(n-max);

    }
    //最长递增子序列
   //dp1= [1, 1, 1, 2, 2, 1, 3, 4]
    private static int[] maxIncr(int[] nums) {
        int dp[]=new int[nums.length];
        dp[0]=1;
        for(int i = 1; i< nums.length; i++)
        {
            int max=0;
            for(int j=0;j<i;j++){
                if(nums[i]> nums[j]){
                    max=Math.max(max,dp[j]);
                }
        }
            dp[i]=max+1;
        }
        return dp;
    }
    //最长递减子序列
    //dp2[]=[3, 3, 2, 3, 2, 1, 1, 1]
    private static int[] maxDecr(int[] nums) {
        int dp[]=new int[nums.length];
        dp[nums.length-1]=1;
        for(int i = nums.length-1; i>=0; i--)
        {
            int max=0;
            for(int j=i+1;j<nums.length;j++){
                if(nums[i]> nums[j]){
                    max=Math.max(max,dp[j]);
                }
            }
            dp[i]=max+1;
        }
        return dp;
    }
}

发表于 2023-02-27 14:25:18 回复(0)
Java
好想要offer的菜鸡头像 好想要offer的菜鸡
最长子序列问题，找出最大的递增和递减之和，就解决这道题了。
发表于 2023-01-09 13:09:47 回复(1)
Java
树荫下的天空头像 树荫下的天空 
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            int n = in.nextInt();
            int[] height = new int[n];
            for (int i = 0; i < n; i++) {
                height[i] = in.nextInt();
            }
            System.out.println(dp(height));
        }
    }

    private static int dp(int[] height) {
        int n = height.length;
        int min = n;
//        dp[i]: 以i结尾的最长上升子序列数量（不包括dp[i]）
        int[] dpLas = new int[n];
//        dp[i]: 以i开头的最长下降子序列数量（不包括dp[i]）
        int[] dpLds = new int[n];
        for (int i1 = 0, i2 = n - 1; i1 < n; i1++, i2--) {
//            先求最长上升子序列
            for (int j = 0; j < i1; j++) {
                if (height[j] < height[i1]) {
                    dpLas[i1] = Math.max(dpLas[i1], dpLas[j] + 1);
                }
            }
//            求最长下降子序列
            for (int j = n - 1; j > i2; j--) {
                if (height[j] < height[i2]) {
                    dpLds[i2] = Math.max(dpLds[i2], dpLds[j] + 1);
                }
            }
        }
        for (int i = 0; i < n; i++) {
//            +1 是包括自身元素
            min = Math.min(n - (dpLds[i] + dpLas[i] + 1), min);
        }
        return min;
    }
}

发表于 2022-11-10 11:39:11 回复(0)
Java
阿木木23333头像 阿木木23333 
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int len = sc.nextInt();
        int[] nums = new int[len];
        for(int i = 0; i < len; i++){
            nums[i] = sc.nextInt();
        }
        int min = len;
        for(int i = 0; i < len; i++){
            int leftNum = left(nums,i);
            int rightNum = right(nums,i);
            // System.out.print(leftNum + " " + rightNum);
            // System.out.println("");
            if(leftNum != 0 && rightNum != 0){
                min = Math.min(min,len - leftNum - rightNum + 1);
            }else if(leftNum == 0 || rightNum == 0){
                min = Math.min(min,len - leftNum - rightNum);
            }
        }
        System.out.println(min);      
    }

    public static int left(int[] nums, int index){
        // if(index == 0){
        //     return 0;
        // }
        int leftNum = 1;
        int[] left_nums = Arrays.copyOfRange(nums,0,index+1);
        // for(int left_num :left_nums){
        //     System.out.print(left_num);
        // }
        // System.out.println("");
        int[] dp1 = new int[left_nums.length];
        Arrays.fill(dp1,1);
        for(int i = 1; i < left_nums.length; i++){
            for(int j = 0; j < i; j++){
                if(left_nums[i] > left_nums[j]){
                    dp1[i] = Math.max(dp1[j] + 1, dp1[i]);
                }
                leftNum = Math.max(leftNum, dp1[i]);
            }
        }
        return leftNum;
    }
    public static int right(int[] nums, int index){
        // if(index == nums.length - 1){
        //     return 0;
        // }
        int rightNum = 1;
        int[] right_nums = Arrays.copyOfRange(nums,index,nums.length);
        // for(int right_num :right_nums){
        //     System.out.print(right_num);
        // }
        // System.out.println("");
        int[] dp2 = new int[right_nums.length];
        Arrays.fill(dp2,1);
        for(int i = 1; i < right_nums.length; i++){
            for(int j = 0; j < i; j++){
                if(right_nums[i] < right_nums[j]){
                    dp2[i] = Math.max(dp2[j] + 1, dp2[i]);
                }
                rightNum = Math.max(rightNum, dp2[i]);
            }
        }
        return rightNum;
    }
}


发表于 2022-09-19 21:41:03 回复(0)
提交观点

问题信息

动态规划 队列
难度：
62条回答 59712浏览

热门推荐

通过挑战的用户

查看代码

相关试题

合唱队

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号