HDU-1257-最小ブロックシステム-LIS

さいしょうブロッキングシステム
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 16661    Accepted Submission(s): 6570
Problem Description
ある国は敵国のミサイル攻撃を防御するために、ミサイル迎撃システムを開発した.しかし、このミサイル迎撃システムには欠陥がある.その最初の砲弾は任意の高さに達することができるが、その後、砲弾ごとに前の砲弾の高さを超えることはできない.ある日、雷達は敵国のミサイル襲撃を捉えた.このシステムはまだ試用段階にあるため、システムは1セットしかない.そのため、すべてのミサイルを遮断できない可能性がある.
どうしようかな?もっとシステムを作ってください.君の言うことは簡単だが,コストは?コストは大きい问题です.だから私はここまで助けを求めに来ました.少なくとも何セットのブロックシステムが必要か计算してください.
 
Input
いくつかのデータを入力します.各データには、ミサイルの総個数(正の整数)、ミサイルが飛来する高さ(レーダーが与える高さデータは30000以下の正の整数で、スペースで区切られています)が含まれています.
 
Output
各組のデータ出力に対応してすべてのミサイルを遮断するには、少なくとも何セットのこのようなミサイル遮断システムが配備される必要があるか.
 
Sample Input

   
   
   
   

    
    
    
    8 389 207 155 300 299 170 158 65
   
   
   
   

 
Sample Output

   
   
   
   

    
    
    
    2
   
   
   
   

 

# include<stdio.h>
# include<string.h>
int arr[30010],lis[30010];
int list(int arr[],int n)    //arr[]        
{
    int i,j,max;        //max           
    max = 0;
    for(i=1;i<=n;i++)
        lis[i] = 1;    //lis[i]   i             ，    1
    
    for(i=2;i<=n;i++)    
    {
        for(j=1;j<i;j++)    //  i      
        {
            if(arr[i]>=arr[j] && lis[i]<lis[j]+1)    
//arr[i]>arr[j]     lis[i]<lis[j] + 1           
                lis[i] = lis[j] + 1;
        }
    }
    
    for(i=1;i<=n;i++)
        if(max < lis[i])
            max = lis[i];
    
    return max;
}

int main()
{
    int n,i,max;
    while(~scanf("%d",&n))
    {
        for(i=1;i<=n;i++)
            scanf("%d",&arr[i]);
        max = list(arr,n);
        printf("%d
",max);
    }
    return 0;
}