Problem description
 
某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。

Input
输入数据为导弹依次飞来的高度，所有高度值均为不大于30000的正整数。

Output
输出只有一行是这套系统最多能拦截的导弹数和要拦截所有导弹最少要配备这种导弹拦截系统的套数。两个数据之间用一个空格隔开.

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