题解 | #合唱队形# java && c++ （小白向）

//本题用动态规划求解 （本人动规初学者以及c++初学者）
// 逆向思维 求最少出队人数 
// 即为 求一个 →（箭头） 形状的数组 中间凸起 两边逐渐下降
//  方法：分别从两个方向求出 该方向的最长递增序列 然后 长出最长的箭头状态数组 数组长度 减去 子序列长度
// 定义 dp_left[n] dp_right[n] 两个数组 分别表示 从左右两个方向起 以第n个数结尾的最长递增子序列 n为数组长度
// 状态转移方程为 ： if(inits[i] > inits[j])dp[i] = max(dp[i],dp[j]+1) 左右都一样，双循环嵌套
// 循环求该方向的最长递增子序列 当inits[i] > inits[j] 时，取 max 值的解释：
// dp[i] 用来存储最大值，不一定是dp【i-1】最大
//因为是最长 !递增！子序列 这个递增很重要 ， 所以不能光第i个元素大于j元素就直接加，必须取决于前面元素的dp大小
// 186 186 150 200 160 130 197 220 例子中，前三个的 dp都为1 所以 200 的dp为 2 
//  还有 1 2 4 3 5 3的dp为 3 ， 但是 5 的dp为 5 ，要比大小取值dp
//  1  3  5  4  7 6  9
// dp-left初始值全设为 1 ，因为最小的子序列为其本身 ，dp-right 不设，全为零，防止重复计算
// 注意 c++中数组默认值不全为0，java的才全是零
//c++ 置零调用memset 方法

#include <bits/stdc++.h> //C++万能库
using namespace std;


int main() {

    std::ios::sync_with_stdio(false); // 解除scanfprin 和 cin cout的同步
    std::cin.tie(nullptr); //解除 cin cout的同步 都是增加速度

    int nums;
    cin>>nums;

    int inits[nums];
    for (int i = 0; i < nums; ++i) {
        cin>>inits[i];
    }

    int dp_left[nums];
    int dp_right[nums];

    for (int i = 0; i < nums; ++i) {
        dp_left[i] = 1;
    }

    for (int i = 0; i <nums ; ++i) {
        for (int j = 0; j <i ; ++j) {
            if (inits[i] > inits[j]){
                dp_left[i] = max(dp_left[i],dp_left[j]+1);
            }
        }
    }

    memset(dp_right,0,sizeof (dp_right));
    for (int i = nums-2; i >= 0 ; i--) {
        for (int j = nums-1; j > i ; j--) {
            if (inits[i] > inits[j]){
                dp_right[i] = max(dp_right[i],dp_right[j]+1);
            }
        }
    }
    int Max = 1;
    for (int i = 0; i < nums; ++i) {
        Max = max(Max,dp_left[i]+dp_right[i]);
    }
    int ans = nums - Max;
    cout<<ans;
    return 0;
}

import java.io.*;
import java.util.Arrays;

public class Main {
	public static void main(String[] args) throws IOException {
	
	  StreamTokenizer streamTokenizer = 
	  new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
	  PrintWriter printWriter  = new PrintWriter(new OutputStreamWriter(System.out));
	  streamTokenizer.nextToken();
	  int nums = (int) streamTokenizer.nval;
	  int[] ints = new int[nums];
	  for (int i = 0; i < nums; i++) {
		  streamTokenizer.nextToken();
		  ints[i] = (int) streamTokenizer.nval;
	  }

	  int[] dp_left = new int[nums];
	  int[] dp_right = new int[nums];

	   for(int i=0;i<nums;i++){
		  dp_left[i] =1;
	  }

	  for (int i = 1; i < nums; i++) {
		  for (int j = 0; j < i; j++) {
			  if (ints[i]>ints[j]){
				  dp_left[i] = Math.max(dp_left[i],dp_left[j]+1);
			  }
		  }
	  }

	  for (int i = nums-2; i >= 0; i--) {
		  for (int j = nums-1; j > i ; j--) {
			  if (ints[i]> ints[j]){
				  dp_right[i] = Math.max(dp_right[i],dp_right[j] + 1 );
			  }
		  }
	  }

	  int max = 0;
	  for (int i = 0; i < nums; i++) {
		  max = Math.max(max,dp_left[i] + dp_right[i]);
	  }
	  int out = nums - max;
	  printWriter.println(out);
	  printWriter.flush();
	}
}