题解 | #合唱队形#

dp动态规划 题目是求出最少出来几人满足队形，反向思考 求满足队形的最多人数是多少？ 这个题目左边的身高要比当前身高小，右边也是要比当前身高小并且是线性。与求最长的升序子序列问题类似，只不过本题目需要从两个维度去思考，左边和右边，左边是升序，右边降序。 思路： 单考虑左边， 算上自己总共有几人满足，这与最长的升序子序列可以说是一样了。 单考虑右边，不算自己（左边的时候已经算了， 在算的话，当前的身高会重复一次），总共有几人满足； 最后算出当前位置 左边和右边满足条件的总和， 找出最大值。 输出 num-max 即使题目需要的输出

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        while(in.hasNext()){
            int num  = in.nextInt();
            int[] nums = new int[num];
            for(int i=0;i<num;i++){
                nums[i] = in.nextInt();
            }
            // 连自己 左边 满足条件的最大值
            //  nums[i] > nums[k]   dp[i] = max(dp[i], dp[k] +1);
            int[] dp_l = new int[num];
            // 右边满足条件的最大值
            int[] dp_r = new int[num];
            //初始化  左边包括自己  全部设成1
            for(int i=0;i<num;i++){
                dp_l[i] =1;
            }
            // 求值
            for(int i=1;i<num;i++){
                for(int k=0;k<i;k++){
                    if(nums[i]>nums[k]) dp_l[i] = Math.max(dp_l[i],dp_l[k]+1);
                }
            }
            for(int i=num-2;i>=0;i--){
                for(int k=num-1;k>i;k--){
                    if(nums[i]>nums[k]) dp_r[i] = Math.max(dp_r[i],dp_r[k]+1);
                }
            }
            int max=1;
            for(int i=0;i<num;i++){
                max = Math.max(max, dp_l[i] + dp_r[i]);
            }
            System.out.println(num-max);
        }
    }
}