題目描述
某國為了防御敵國的導彈襲擊，開發出一種導彈攔截系統。但是這種導彈攔截系統有一個缺陷：雖然它的第一發炮彈能夠到達任意的高度，但是以後每一發炮彈都不能高於前一發的高度。某天，雷達捕捉到敵國的導彈來襲，並觀測到導彈依次飛來的高度，請計算這套系統最多能攔截多少導彈。攔截來襲導彈時，必須按來襲導彈襲擊的時間順序，不允許先攔截後面的導彈，再攔截前面的導彈。
輸入
每組輸入有兩行，第一行，輸入雷達捕捉到的敵國導彈的數量k（k<=25），第二行，輸入k個正整數，表示k枚導彈的高度，按來襲導彈的襲擊時間順序給出，以空格分隔。
輸出
每組輸出只有一行，包含一個整數，表示最多能攔截多少枚導彈。
樣例輸入
4
9 6 7 8
7
4 5 6 7 13 42 3
5
6 5 4 3 5
0
樣例輸出
2
2
4
提示 [+]
*** 提示已隱藏，點擊上方 [+] 可顯示 ***
來源
2007年北京大學計算機研究生機試真題
【思路】
具體參考：算法之最長遞增子序列，最長公共子序列
[cpp]
/*********************************
* 日期：2013-3-25
* 作者：SJF0115
* 題號: 題目1085: 攔截導彈
* 來源：http://acmclub.com/problem.php?id=1085
* 結果：AC
* 來源：2007年北京大學計算機研究生機試真題
* 總結：
**********************************/
#include<stdio.h>
#include<string.h>
int Height[26];
int MaxLen[26];
void LIS(int k){
memset(MaxLen,0,sizeof(MaxLen));
for(int i = 1;i <= k; i++){
MaxLen[i] = 1;
//遍歷其前所有導彈高度
for(int j = 1;j < i;j++){
//如果當前導彈高度小於等於j號導彈
if(Height[i] <= Height[j]){
//把當前導彈放在j號導彈後，其最長不增子序列長度為j號導彈結尾的最長不增子序列長度 + 1
int preMax = MaxLen[j] + 1;
if(preMax > MaxLen[i]){
MaxLen[i] = preMax;
}
}
}
}
}
int main()
{
int N,i;
//freopen("C:\\Users\\SJF\\Desktop\\acm.txt","r",stdin);
while(scanf("%d",&N)!=EOF){
//輸入導彈高度
for(i = 1;i <= N;i++){
scanf("%d",&Height[i]);
}
LIS(N);
int Max = -1;
//輸出最長不增子序列的長度即能攔截的導彈數
for(i = 1;i <= N;i++){
if(Max < MaxLen[i]){
Max = MaxLen[i];
}
}
if(N != 0){
printf("%d\n",Max);
}
}
return 0;
}
/*********************************
* 日期：2013-3-25
* 作者：SJF0115
* 題號: 題目1085: 攔截導彈
* 來源：http://acmclub.com/problem.php?id=1085
* 結果：AC
* 來源：2007年北京大學計算機研究生機試真題
* 總結：
**********************************/
#include<stdio.h>
#include<string.h>
int Height[26];
int MaxLen[26];
void LIS(int k){
memset(MaxLen,0,sizeof(MaxLen));
for(int i = 1;i <= k; i++){
MaxLen[i] = 1;
//遍歷其前所有導彈高度
for(int j = 1;j < i;j++){
//如果當前導彈高度小於等於j號導彈
if(Height[i] <= Height[j]){
//把當前導彈放在j號導彈後，其最長不增子序列長度為j號導彈結尾的最長不增子序列長度 + 1
int preMax = MaxLen[j] + 1;
if(preMax > MaxLen[i]){
MaxLen[i] = preMax;
}
}
}
}
}
int main()
{
int N,i;
//freopen("C:\\Users\\SJF\\Desktop\\acm.txt","r",stdin);
while(scanf("%d",&N)!=EOF){
//輸入導彈高度
for(i = 1;i <= N;i++){
scanf("%d",&Height[i]);
}
LIS(N);
int Max = -1;
//輸出最長不增子序列的長度即能攔截的導彈數
for(i = 1;i <= N;i++){
if(Max < MaxLen[i]){
Max = MaxLen[i];
}
}
if(N != 0){
printf("%d\n",Max);
}
}
return 0;
}
