题解 | #合唱队#
合唱队
https://www.nowcoder.com/practice/6d9d69e3898f45169a441632b325c7b4
import java.util.Arrays; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); while (sc.hasNext()) { int n = sc.nextInt(); int[] Q = new int[n]; for (int i = 0; i < n; i++) { Q[i] = sc.nextInt(); } //填左侧动态规划表 Main m4 = new Main(); int[] resl = m4.DTGHtable(Q); //队列倒置后,填右侧动态规划表 int[] Q0 = Arrays.copyOf(Q, Q.length); for (int j = 0; j < Q0.length; j++) { Q0[j] = Q[Q.length - 1 - j]; }; int[] resr = m4.DTGHtable(Q0); //左侧结果+右侧结果+1,排序后取最大值,输出(总人数-这个最大值) int[] res = new int[Q.length]; for (int i = 0; i < res.length; i++) { res[i] = resl[i + 1] + resr[resr.length - 1 - i] + 1; } Arrays.sort(res); System.out.println(n - res[res.length - 1]); } } //填动态规划表的方法 public int[] DTGHtable(int T[]) { int n = T.length; int[][] table = new int[n + 1][n + 1]; int[] Ti = Arrays.copyOf(T, n); //首行首列设为0 for (int i = 0; i < n + 1; i++) { table[i][0] = 0; } for (int j = 0; j < n + 1; j++) { table[0][j] = 0; } //从第1列1行开始填 for (int i = 1; i < n + 1; i++) { for (int j = 1; j < n + 1; j++) { if (i < j && Ti[i - 1] < T[j - 1]) {//合适时的取值公式 table[i][j] = Math.max(1 + table[i - 1][i], table[i - 1][j]); } else if ((i >= j) || (Ti[i - 1] >= T[j - 1])) {//不合适时的取值公式 table[i][j] = table[i - 1][j]; } } } return table[table.length-1]; } }