1322：【例6.4】攔截導彈問題(Noip1999)

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

【題目描述】

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

輸入導彈依次飛來的高度（雷達給出的高度不大于30000的正整數）。計算要攔截所有導彈最小需要配備多少套這種導彈攔截系統。

【輸入】

n顆依次飛來的高度（1≤n≤1000）。

【輸出】

要攔截所有導彈最小配備的系統數k。

【輸入樣例】

389 207 155 300 299 170 158 65

【輸出樣例】

2

【提示】

輸入：導彈高度： 4 ?3 ?2

輸出：導彈攔截系統k=1

【分析】

? ? ? ?這道題的思路是令每套裝置的價值最大化。也就是說，避免讓一個剛攔截了300m導彈的裝置攔截50m的，而剛攔截60m導彈的裝置就可以攔截它。首先，第一發導彈是必須要用一套新的裝置的。而第二發就有兩種情況：比第一發高，只能再開一套；比第一發矮，使用第一套攔截。到了第i發導彈，就已經有u套裝置。那么從小到大枚舉裝置能攔截的導彈高度，然后選擇剛好能攔截i的最小的裝置，就能最大限度減小浪費。如果所有裝置都無法攔截，那么就新開一個裝置來攔截。

感謝題解：https://www.cnblogs.com/Wild-Donkey/p/12323370.html

【參考代碼】

#include <stdio.h> #define N 1010 int l[N]; //攔截系統 int s[N]; //導彈高度 int main() {int i,j,p,n=1,k=1;while(scanf("%d",&s[n])!=EOF)n++;l[k]=s[1]; //使用新的裝置攔截第一個導彈for(i=2;i<=n;i++) //枚舉每個導彈 {p=0; //標記位，是否是可攔截的最小值 for(j=1;j<=k;j++) //枚舉用哪個裝置{if(l[j] >= s[i]) //找到能攔截的第一套裝置{if(p==0)p=j;else if(l[p] > l[j]) //貪心，更新裝置 p=j;}}if(p==0) //無法攔截 {k++; l[k]=s[i]; //增加一套新的系統，并且放在最后 }else //貪心，更新第p套系統的最低高度{l[p]=s[i];}}printf("%d\n",k);return 0; }

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

總結

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

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