「线性DP」合唱队形

合唱队形

https://ac.nowcoder.com/acm/contest/24213/1011

题目描述

合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1，2…，K，他们的身高分别为T1，T2，…，TK， 则他们的身高满足T1<…Ti+1>…>TK(1<=i<=K)。
你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。

输入描述

输入的第一行是一个整数N(2<=N<=100)，表示同学的总数。第一行有n个整数，用空格分隔，第i个整数Ti(130<=Ti<=230)是第i位同学的身高(厘米)。

输出描述

输出包括一行，这一行只包含一个整数，就是最少需要几位同学出列。

样例

8
186 186 150 200 160 130 197 220

4

提示

• 对于50％的数据，保证有n<=20；
• 对于全部的数据，保证有n<=100。

解析

不难看出来，由顶峰左边是从小到大，右边是从大到小的一个增长趋势，对应着就是 LIS 和 LDS，求出来后得到：

LIS: 1 1 1 2 2 1 3 4 
LDS: 3 3 2 3 2 1 1 1

最终合唱队形的总人数为：$LIS[i]+LDS[i]-1$

最终要踢掉的人数：总人数 - 合唱人数

代码

import java.io.*;
import java.util.*;
import java.math.*;public class Main {static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));static StreamTokenizer st = new StreamTokenizer(br);static PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));public static void main(String[] args) throws Exception {int n = nextInt();int[] A = new int[n + 1];int[] LIS = new int[n + 1];int[] LDS = new int[n + 1];Arrays.fill(LIS, 1);Arrays.fill(LDS, 1);for(int i = 1; i <= n; i++) A[i] = nextInt();for(int i = 2; i <= n; i++) {for(int j = 1; j < i; j++) {if(A[i] > A[j]) LIS[i] = Math.max(LIS[i], LIS[j] + 1);}}for(int i = n - 1; i > 0; i--) {for(int j = n; j > i; j--) {if(A[i] > A[j]) LDS[i] = Math.max(LDS[i], LDS[j] + 1);}}int ans = 10000;for(int i = 1; i <= n; i++) {ans = Math.min(ans, n - (LIS[i] + LDS[i] - 1));}System.out.println(ans);}public static int nextInt() throws Exception {st.nextToken();return (int) st.nval;}
}

书本小说网