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

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

 
Output
输出只有一行是这套系统最多能拦截的导弹数和要拦截所有导弹最少要配备这种导弹拦截系统的套数。

两个数据之间用一个空格隔开.

 
Sample Input
389 207 155 300 299 170 158 65
 
Sample Output
6 2
 
Problem Source
NOI 99

 
// my code

#include <stdio.h>

int a[10000],b[10000];

int main(){
 int i,j,k,m,n,maxr,maxt;

 for(i = 0; scanf("%d",&a[i]) != EOF; i++)
  ;
 for(maxr = 1,j = i-1; j >= 0; j--){
  for(maxt = 0,b[j] = 1,k = j+1; k < i; k++){
   if(a[k] <= a[j] && b[k] > maxt)
    maxt = b[k];
  }
  b[j] += maxt;
  maxr = (maxr > b[j] ? maxr : b[j]);
 }
 for(k=0,n=j=1,b[0]=a[0]; j < i; j++){
  for(m=0; m<=k; m++){
   if(a[j] < b[m])
    break;
  }
  if(m <= k)
   b[m] = a[j];
  else {
   b[k+1] = a[j];
   k++;
   n++;
  }
 }
 printf("%d %d\n",maxr,n);
 return 0;
}

评论