Problem description
?
某國為了防御敵國的導彈襲擊，發(fā)展出一種導彈攔截系統(tǒng)。但是這種導彈攔截系統(tǒng)有一個缺陷：雖然它的第一發(fā)炮彈能夠到達任意的高度，但是以后每一發(fā)炮彈都不能高于前一發(fā)的高度。某天，雷達捕捉到敵國的導彈來襲。由于該系統(tǒng)還在試用階段，所以只有一套系統(tǒng)，因此有可能不能攔截所有的導彈。

Input
輸入數(shù)據(jù)為導彈依次飛來的高度，所有高度值均為不大于30000的正整數(shù)。

Output
輸出只有一行是這套系統(tǒng)最多能攔截的導彈數(shù)和要攔截所有導彈最少要配備這種導彈攔截系統(tǒng)的套數(shù)。兩個數(shù)據(jù)之間用一個空格隔開.

Sample Input
389 207 155 300 299 170 158 65
?
Sample Output
6 2


第一問顯然是求最長不下降序列長度
第二問求最長上升序列長度

?1 #include? < iostream >
?2 #include? < vector >
?3
?4 using ? namespace ?std;
?5
?6 int ?main()
?7 {
?8 ????vector < int > ??a;
?9 ???? int ????data;
10
11 ???? while ?(?cin? >> ?data?)
12 ????????a.push_back(?data?);
13
14 ???? int ???len = ?static_cast < int > (?a.size?()?);
15 ???? int * ??value = ? new ? int [len];
16 ???? int ???max,?t = ? 0 ;
17
18 ???? for ?(? int ?i = ? 0 ;?i < ?len;? ++ i?)
19 ????????value[i] = ? 1 ;
20
21 ???? for ?(? int ?i = ? 0 ;?i < ?len;? ++ i?)
22 ???? {
23 ????????max = ? 0 ;
24 ????????t = ? 0 ;
25
26 ???????? for ?(? int ?j = ? 0 ;?j < ?i;? ++ j?)
27 ???????????? if ?(?a[i] < ?a[j]? && ?value[j] > ?max?)
28 ???????????? {
29 ????????????????t = ? 1 ;
30 ????????????????max = ?value[j];
31 ????????????}
32
33 ???????? if ?(?t != ? 0 ?)
34 ????????????value[i] = ?max + ? 1 ;
35 ????}
36
37 ????max = ? 1 ;
38 ???? for ?(? int ?i = ? 0 ;?i < ?len;? ++ i?)
39 ???????? if ?(?value[i] > ?max?)
40 ????????????max = ?value[i];
41
42 ????cout? << ?max;
43
44 ???? for ?(? int ?i = ? 0 ;?i < ?len;? ++ i?)
45 ????????value[i] = ? 1 ;
46
47 ???? for ?(? int ?i = ? 0 ;?i < ?len;? ++ i?)
48 ???? {
49 ????????max = ? 0 ;
50 ????????t = ? 0 ;
51
52 ???????? for ?(? int ?j = ? 0 ;?j < ?i;? ++ j?)
53 ???????????? if ?(?a[i] > ?a[j]? && ?value[j] > ?max?)
54 ???????????? {
55 ????????????????t = ? 1 ;
56 ????????????????max = ?value[j];
57 ????????????}
58
59 ???????? if ?(?t != ? 0 ?)
60 ????????????value[i] = ?max + ? 1 ;
61 ????}
62
63 ????max = ? 1 ;
64 ???? for ?(? int ?i = ? 0 ;?i < ?len;? ++ i?)
65 ???????? if ?(?value[i] > ?max?)
66 ????????????max = ?value[i];
67
68 ????cout? << ? ' ? ' ? << ?max;
69
70 ???? return ? 0 ;
71 }
72