HDU最小ブロックシステム(dp)

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

8 389 207 155 300 299 170 158 65

Sample Output

2

Source
浙江工業大学第4回大学生プログラム設計コンテスト
ACコード:

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
int main(){
    int n;
    int dp[1111],i,j,a[1111];
    while(cin>>n){
        int out=0;
        for(i=0;i<n;++i){
            cin>>a[i];
            dp[i]=1;
        }
        for(i=0;i<n;++i){
            for(j=i-1;j>=0;--j){
                if(a[i]>a[j]&&dp[j]+1>dp[i])
                dp[i]=dp[j]+1;
            }
        out=out>dp[i]?out:dp[i];
        }
        printf("%d
",out);
    }
    return 0;
}