华为OJ-合唱队

吸毒的虫子

华为OJ-初级题-合唱队

思路与分析
　　本题可以用DP的方法，分别从正向和逆向的两个方向求，该数组即186 186 150 200 160 130 197 200的上升对大序列。正向为[1, 1, 1, 2, 2, 1, 3, 4]，逆向为[3, 3, 2, 3, 2, 1, 1, 1]。
　　然后将两个序列相加取最大值为5，根据题意出列的人数为N -（5 - 1）。注：减去1的原因是为中间的数被正序和逆序加了两次。
　　第一次做这种题表示很蒙蔽<`_`>~那么下面是源码。

本题参考代码





1 import java.util.Arrays;
2 import java.util.Scanner;
3 /**
4  * 合唱队
5  * array[]：待处理数据
6  * Inc[]:正向遍历得到上升的最大序列
7  * Dec[]:逆向遍历得到上升的最大序列
8  *
9  * Created by Evan on 2016-8-29.
10  */
11 public class ChorusDp {
12     
13     public static void main(String []args){
14         Scanner sc = new Scanner(System.in);
15         while(sc.hasNext()){
16             int N = sc.nextInt();
17             int [] array = new int [N];
18             int [] Inc = new int [N];
19             int [] Dec = new int [N];
20             for( int i = 0; i < N;i++){
21                 array = sc.nextInt();
22             }
23             //正向遍历得到上升的最大序列的个数是多少，本题为[1, 1, 1, 2, 2, 1, 3, 4]
24            
25             Inc[0] = 1;
26             for( int i = 1; i < N ; i++){
27                 Inc = 1;
28                 for( int j = 0 ; j < i;j++){
29                     if(array > array[j] && Inc[j] + 1 > Inc){
30                         Inc = Inc[j] + 1;
31                     }
32                 }
33             }
34             //System.out.println(Arrays.toString(Inc));
35             //逆向最长上升序列的个数，本题为[3, 3, 2, 3, 2, 1, 1, 1]
36             Dec[N - 1] = 1;
37             for(int i = N - 2; i >=0; i--){
38                 Dec = 1;
39                 for(int j = N - 1; j > i; j--){
40                     if(array > array[j] && Dec[j] + 1 > Dec){
41                         Dec = Dec[j] + 1;
42                     }
43                 }
44             }
45             //System.out.println(Arrays.toString(Dec));
46             int temp = Inc[0] + Dec[0];
47             for(int i = 1; i < N ;i++){
48                 if(Inc + Dec > temp){
49                     temp = Inc + Dec;
50                 }
51             }
52             System.out.println(N - temp + 1);//减去1是因为中间的那个数加了两次。
53         }
54     }
55     
56 }
合唱队