描述
某國為了防御敵國的導彈襲擊，開發出一種導彈攔截系統。但是這種導彈攔截系統有一個缺陷：雖然它的第一發炮彈能夠到達任意的高度，但是以後每一發炮彈都不能高於前一發的高度。某天，雷達捕捉到敵國的導彈來襲，並觀測到導彈依次飛來的高度，請計算這套系統最多能攔截多少導彈。攔截來襲導彈時，必須按來襲導彈襲擊的時間順序，不允許先攔截後面的導彈，再攔截前面的導彈。
輸入
輸入有兩行，
第一行，輸入雷達捕捉到的敵國導彈的數量k（k<=25），
第二行，輸入k個正整數，表示k枚導彈的高度，按來襲導彈的襲擊時間順序給出，以空格分隔。
輸出
輸出只有一行，包含一個整數，表示最多能攔截多少枚導彈。
樣例輸入
8 300 207 155 300 299 170 158 65
樣例輸出
6
代碼如下：
1 #include <cstdio>
2 int main()
3 {
4 int k,arr[30],a[30] = {0},ans = 0;
5 scanf("%d",&k);
6 for(int i=0;i<k;i++){
7 scanf("%d",&arr[i]);
8 int max=0;
9 for(int j=i-1;j>=0;j--){
10 if(arr[i]<=arr[j] && max < a[j]){
11 max = a[j];
12 }
13 }
14 a[i] = max + 1;
15 if(ans < a[i]){
16 ans = a[i];
17 }
18 }
19 printf("%d\n",ans);
20
21 return 0;
22 }
解析
經典DP，最長降序子序列問題。
arr數組儲存的是導彈的高度。a數組儲存的是對應arr的導彈高度為最長降序子序列最後出現的導彈（如a[0]就是arr[0]為降序序列最後出現的導彈）時攔截導彈的最大個數。
（eg:本題的arr分別為{300,207,155,300,299,170,158,65}.那麼a對應的分別為{1(300),2(300,207),3(300,207,155),2(300,300),3(300,300,299),4(300,300,299,170),5(300,300,299,170,158),6(300,300,299,170,158,65)}）
尋找a數組中的最大值即為本題的答案啦。
