题解 | #合唱队#
合唱队
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];
}
}
投递美团等公司9个岗位