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

输出
这套系统最多能拦截多少导弹

例如
int a[]={300,250,275,252,200,138,245};    // 高度数据，直接写在程序里，以方便测试

[ 本帖最后由 hwdwow 于 2009-10-5 07:09 编辑 ]

前几天看到过一朋友发过，回帖的那个程序个根本不能运行

个人认为不会太简单

呃~~没达到那个程度呢~

a[]={300,250,275,252,200,138,245};  这表示高度的数据是不变的嘛，还是举个例子说明一下。
要是导弹的高度就是这几个，那我觉得最多能拦截4枚。是不是啊，要是不是，说明我还没有理解题意。

答案是5
300,275,252,200,138

我明白了，是我没看到最多的组合，是5枚。

[ 本帖最后由 m456m654 于 2009-10-4 22:27 编辑 ]

用组合法最多能算到n=20左右

我理解是下面这样：
列1：
输入：300 250 275 252 200 138 245 -1   （程序是以 -1 结束）
显示：
5
300 275 252 200 138
（拦截5 ，显示拦截哪5个）
·
列2：
输入：100 260 280 260 210 166 199 -1
4
280 260 210 166
（拦截4 ，显示拦截哪4个）

#include<stdio.h> 
#include<malloc.h> 
int main(void) 
{ 
    int i,j,k,k1,x,n,m,max_len=0,max,a_len=0; 
    int y,**a,*p; 
 
    while(1) 
      { 
       scanf("%d",&y); 
       if(y==-1)break; 
       p=(int *)malloc(sizeof(int)); 
       *p=y; 
       a[a_len]=p; /* a[a_len]乱指一个地址了，我这错了。要更正只能在前面加代码分配空间，输入总的导弹数才行  */  
       a_len++; 
      } 
 
 
    p=(int *)malloc(sizeof(int)*a_len); 
 
    for(k=0;k<a_len-2;k++) 
      { 
       x=*a[k]; 
       n=1; 
       for(i=k+1;i<a_len-1;i++) 
    { 
     if(x>*a[i]) 
       { 
        m=*a[i]; 
        n=2; 
        for(j=i+1;j<a_len;j++) 
          { 
          if(m>*a[j]) 
        { 
         n++; 
         m=*a[j]; 
        } 
          } 
       } 
     if(max_len<n) 
        { 
         max_len=n; 
         m=p[0]=max=*a[k]; 
         for(j=i,k1=1;j<a_len;j++) 
           { 
        if(m>*a[j]) 
          { 
           p[k1]=*a[j]; 
           m=*a[j]; 
           k1++; 
          } 
           } 
         if(k<a_len) 
           p[k1]=-1; 
        } 
     if((a_len-i-1)<n)break; 
    } 
    if(a_len-2-k<max_len)break; 
       } 
 
 
    printf("%d\n",max_len); 
    for(i=0;i<a_len;i++) 
      { 
       if(p[i]==-1)break; 
       printf("%d ",p[i]); 
      } 
    printf("\n\n"); 
 
    getch(); 
    return 0; 
}

[ 本帖最后由 UserYuH 于 2009-10-5 00:57 编辑 ]

最大不下降序列呀……