HJ24 合唱队——动态规划

HJ24 合唱队

解析：这道题可以参考该视频的思路，使用left和right数组记录元素i左边递增的元素个数和右边递减元素的个数。left和right数组的值由前面的状态推出，如果i比前面的某一元素ii大，则left[i] = max(left[i], left[ii] 1),最后只需把left和right加起来减一即是合唱队剩余人数。
注意：这道题在牛客上用python运行显示超时，用Java可以通过。

# python
n = int(input())
list = [] 
left = [1] * n    # left[i]表示0~i位置上最长的递增子序列的长度
right = [1] * n    # # right[i]表示i~n-1位置上最长的递减子序列的长度
res = 0
list = [int(n) for n in input().split(' ')]
for i in range(n):
    for ii in range(i):
        if list[i] > list[ii]:
            left[i] = max(left[i], left[ii]   1)    # 动态规划，取最大值
for j in range(n - 1, -1, -1):
    for jj in range(n - 1, j, -1):
        if list[j] > list[jj]:
            right[j] = max(right[j], right[jj]   1)
for i in range(n):
    res = max(res, left[i]   right[i])       # left[i]   right[i]表示组成合唱队人数，最高值多加了一次
print(n - res   1)

// Java
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()) {
            int n = sc.nextInt();
            int[] list = new int[n];
            for (int i = 0; i < n; i  ) {
                list[i] = sc.nextInt();
            }
            int[] left = new int[n];
            int[] right = new int[n];
            for (int i = 0; i < n; i  ) {
                left[i] = 1;
                for (int ii = 0; ii < i; ii  ) {
                    if (list[i] > list[ii]) {
                        left[i] = Math.max(left[i], left[ii]   1);
                    }
                }
            }
            for (int j = n - 1; j >= 0; j--) {
                right[j] = 1;
                for (int jj = n - 1; jj > j; jj--) {
                    if (list[j] > list[jj]) {
                        right[j] = Math.max(right[j], right[jj]   1);
                    }
                }
            }
            int res = 0;
            for (int i = 0; i < n; i  ) {
                res = Math.max(res, left[i]   right[i]);
            }
            System.out.println(n - res   1);
        }
    }
}

这篇好文章是转载于：学新通技术网