228
京東網上商城
九度題目1112：攔截導彈
題目1112：攔截導彈時間限製：1 秒內存限製：32 兆特殊判題：否提交：1842解決：873
題目描述：
某國為了防禦敵國的導彈襲擊，開發出一種導彈攔截係統。但是這種導彈攔截係統有一個缺陷：雖然它的第一發炮彈能夠到達任意的高度，但是以後每一發炮彈都不能高於前一發的高度。某天，雷達捕捉到敵國的導彈來襲，並觀測到導彈依次飛來的高度，請計算這套係統最多能攔截多少導彈。攔截來襲導彈時，必須按來襲導彈襲擊的時間順序，不允許先攔截後麵的導彈，再攔截前麵的導彈。
輸入：
每組輸入有兩行，
第一行，輸入雷達捕捉到的敵國導彈的數量k（k<=25），
第二行，輸入k個正整數，表示k枚導彈的高度，按來襲導彈的襲擊時間順序給出，以空格分隔。
輸出：
每組輸出隻有一行，包含一個整數，表示最多能攔截多少枚導彈。
樣例輸入：
8
300 207 155 300 299 170 158 65
樣例輸出：
6
來源：
2007年北京大學計算機研究生機試真題
//最長單調上升子序列
AC代碼：
#include<stdio.h>
#include<string.h>
int a[30];
int Fun(int a[],int m)//求最長上升子序列
{
int i,j,max=0,num[30];
for(i=0;i<m;i++)
num[i]=1;
for(i=1;i<m;i++)
for(j=0;j<i;j++)
if(a[i]>=a[j]&&num[i]<num[j]+1)
num[i]=num[j]+1;
for(i=0;i<m;i++)
{
if(num[i]>max)
max=num[i];
}
return max;
}
int main()
{
int i,j,n,m;
while(scanf("%d",&n)!=EOF)
{
memset(a,0,sizeof(a));
for(i=n-1;i>=0;i--)//將數組逆置，方便求最長“上升”子序列
scanf("%d",&a[i]);
printf("%d\n",Fun(a,n));//忘打換行了，WA幾次⊙﹏⊙b汗
}
return 0;
}
最後更新：2017-04-03 05:38:58