华为OJ-合唱队
华为OJ-初级题-合唱队思路与分析
本题可以用DP的方法，分别从正向和逆向的两个方向求，该数组即186 186 150 200 160 130 197 200的上升对大序列。正向为，逆向为。
然后将两个序列相加取最大值为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 ;
18 int [] Inc = new int ;
19 int [] Dec = new int ;
20 for( int i = 0; i < N;i++){
21 array = sc.nextInt();
22 }
23 //正向遍历得到上升的最大序列的个数是多少，本题为
24
25 Inc = 1;
26 for( int i = 1; i < N ; i++){
27 Inc = 1;
28 for( int j = 0 ; j < i;j++){
29 if(array > array && Inc + 1 > Inc){
30 Inc = Inc + 1;
31 }
32 }
33 }
34 //System.out.println(Arrays.toString(Inc));
35 //逆向最长上升序列的个数，本题为
36 Dec = 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 && Dec + 1 > Dec){
41 Dec = Dec + 1;
42 }
43 }
44 }
45 //System.out.println(Arrays.toString(Dec));
46 int temp = Inc + Dec;
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 }
合唱队
页:
[1]