1260：【例9.4】攔截導彈(Noip1999)

時間限制: 1000 ms ??? ??? 內存限制: 65536 KB
提交數: 15078 ??? 通過數: 5806

【題目描述】

某國為了防御敵國的導彈襲擊，發展出一種導彈攔截系統。但是這種導彈攔截系統有一個缺陷：雖然它的第一發炮彈能夠到達任意的高度，但是以后每一發炮彈都不能高于前一發的高度。某天，雷達捕捉到敵國的導彈來襲。由于該系統還在試用階段，所以只有一套系統，因此有可能不能攔截所有的導彈。

輸入導彈依次飛來的高度（雷達給出的高度數據是不大于30000的正整數，導彈數不超過1000），計算這套系統最多能攔截多少導彈，如果要攔截所有導彈最少要配備多少套這種導彈攔截系統。

【輸入】

輸入導彈依次飛來的高度。

【輸出】

第一行：最多能攔截的導彈數；

第二行：要攔截所有導彈最少要配備的系統數。

【輸入樣例】

389 207 155 300 299 170 158 65

【輸出樣例】

6 2

【分析】

? ? ? ? 第一問最長不上升子序列問題。用a[x]表示原序列中第 x 個元素，b[x]表示長度為 x的不下降子序列的長度。當處理 a[x]時，可查找它可以連接到長度最大為多少的不下降子序列后（即與部分 b[x]比較）。假設可以連到長度最大為 maxn的不下降子序列后，則 b[x]=maxn十1。b 數組被賦值的最大值就是第一問的答案。
? ? ? ? 第二問最長不下降子序列問題。

【參考代碼】

#include <stdio.h> #define N 1010int dp1[N]; //第一問，最長不上升子序列 int dp2[N]; //第二問，最長不下降之序列 int f[N]; //導彈序列 int max(int x,int y) {return x > y ? x : y; }int main() {int idx=0,ans=0,cnt=0;int i,j;while(scanf("%d", &f[idx])!=EOF) //遇到文件尾自動結束 Ctrl+Eidx++;for(i=0;i<idx;i++){dp1[i]=dp2[i]=1;for(j=0;j<i;j++){if(f[i]<=f[j]) // 最長不上升子序列dp1[i]=max(dp1[i],dp1[j]+1);else // 最長不下降子序列dp2[i]=max(dp2[i],dp2[j]+1);}if(ans<dp1[i])ans=dp1[i];if(cnt<dp2[i])cnt=dp2[i];}printf("%d\n%d\n",ans,cnt);return 0; }

http://ybt.ssoier.cn:8088/problem_show.php?pid=1260

總結

以上是生活随笔為你收集整理的信息学奥赛一本通（1260：【例9.4】拦截导弹(Noip1999)）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。