题解 | #合唱队#

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int len = in.nextInt();
        int[] arr = new int[len];
        int[] left = new int[len];
        int[] right = new int[len];

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

        left[0] = 0;
        for (int i = 1; i < len; i++) {
            int min = i;
            for (int j = i - 1; j >= 0; j--) {
                if (arr[j] < arr[i] && left[j] + i - j - 1 < min) {
                    min = left[j] + i - j - 1;
                } 
            }
            left[i] = min;
        }

        right[len - 1] = 0;
        for (int i = len - 2; i >= 0; i--) {
            int min = len - i - 1;
            for (int j = i + 1; j < len; j++) {
                if (arr[j] < arr[i] && right[j] + j - i - 1 < min) {
                    min = right[j] + j - i - 1;
                } 
            }
            right[i] = min;
        }

        int min = len;
        for (int i = 0; i < len; i++) {
            if (left[i] + right[i] < min) {
                min = left[i] + right[i];
            }
        }
        System.out.println(min);

        // for (int i = 0; i < len; i++) {
        //     System.out.print(left[i] + " ");
        // }
        // System.out.println();

        // for (int i = 0; i < len; i++) {
        //     System.out.print(right[i] + " ");
        // }
        // System.out.println();

    }
}

动态规划：

寻找合唱队列（使出列人数最少）=寻找某点左侧递增、右侧递减（使出列人数最少）

构建数组left[i]，使从1号至i号递增（以i结尾）最少出列人数。

left[1]=0,

left[i] = min(left[j] + i - j -1), 条件：1<j<i, arr[j]<arr[i]，j为i递增队列的前序节点，j至i之间节点全部出列

构建数组right[i]，使从n号至i号递增（以i结尾）最少出列人数。逻辑以left相同

最后寻找点位i，使left[i]+right[i]最小