NYOJ-79:迎撃ミサイル

迎撃ミサイル.
出典:NYOJタグ:動的計画参考資料:類似テーマ:http://blog.csdn.net/wingrez/article/details/78137249
タイトル
ある国は敵国のミサイル攻撃を防ぐために、ミサイル迎撃システムを発展させた.しかし、このミサイル迎撃システムには欠陥がある.最初の砲弾は任意の高さに達することができるが、その後、各砲弾は前の砲弾に等しい高さを超えてはならない.ある日、レーダーは敵国ミサイルの襲撃を捉えた.このシステムはまだ試用段階にあるため、1つのシステムしか使わないため、すべてのミサイルを遮断できない可能性がある.
入力
1行目の入力試験データ群数N(1<=N<=10)次の行は、この試験データ群のミサイルmが何個あるかを入力し(1<=m<=20)次の行入力ミサイルが順次飛来する高さであり、すべての高さ値は0より大きい正の整数である.
しゅつりょく
最大遮断可能なミサイル数を出力
入力サンプル
2 8 389 207 155 300 299 170 158 65 3 88 34 65
出力サンプル
6 2
リファレンスコード

#include
int main(){
	int N;
	scanf("%d",&N);
	while(N--){
		int m;
		scanf("%d",&m);
		int arr[m],dp[m]; 
		int i,j;
		int res=0;
		for(i=0;i<m;i++)
			scanf("%d",&arr[i]);
			
		for(i=0;i<m;i++){
			dp[i]=1;
			for(j=0;j<i;j++){
				if(arr[j]>arr[i]){
					dp[i]= dp[i]>dp[j]+1 ? dp[i] : dp[j]+1;
				}
			}
			res= res>dp[i] ? res:dp[i];
		}
		printf("%d
",res);
	}
	return 0;
}