題目描述

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

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

輸入輸出格式

輸入格式：

1?行，若干個整數（個數 ≤100000?）

輸出格式：

2?行，每行一個整數，第一個數字表示這套系統最多能攔截多少導彈，第二個數字表示如果要攔截所有導彈最少要配備多少套這種導彈攔截系統。

輸入輸出樣例

輸入樣例#1：

389 207 155 300 299 170 158 65

輸出樣例#1：

6
2

思路：線性DP經典題，由于超時問題，最后用記憶化+二分解決問題

源代碼

#include<iostream> #include<cstdio> #include<cstring> using namespace std;int max(int x,int y)//比較函數 {if(x>y)return x;elsereturn y; }int missile[100010],dp[100010]; int main() {int n=0,total=0,ans=0;int i;int a,b,mid;while(scanf("%d",&missile[++n])!=EOF);//表示資料源無更多的資料可讀取，通常在文本的最后存在此字符表示資料結束，輸入時，以ctrl+z為結束/*求最長不上升子序列*/dp[0]=99999;//由于導彈最高高度為50000，因此初始化為極大值for(i=1;i<=n-1;i++){if(dp[total]>=missile[i])//比較最大高度與導彈高度{dp[total+1]=missile[i];//記錄當前最大高度total++;//最長子序列加一}else//二分查找+記憶化，縮短時間{a=0;b=total;//左右區間while(a<b){mid=(a+b)/2;//取中if(dp[mid]>=missile[i])//中點高度＞=當前導彈高度a=mid+1;//左區間變為當前導彈高度向后1位else//中點高度<當前導彈高度b=mid;//右區間變為當前導彈高度}if(a!=0) dp[a]=missile[i];//當左區間不為0時，令左區間起始高度變為當前導彈高度}}cout<<total<<endl;//輸出最長子序列長度/*求最長上升子序列*/memset(dp,0,sizeof(dp));//將數組全部賦0值for(i=1;i<=n-1;i++){if(dp[ans]<missile[i])//比較系統最大高度與導彈高度{dp[ans+1]=missile[i];//記錄最大高度ans++;//所需系統數+1}else//二分查找+記憶化，縮短時間{a=0;b=ans;//左右區間while(a<b){mid=(a+b)/2;//取中if(dp[mid]>=missile[i])//中點高度＞=當前導彈高度b=mid;//右區間變為當前導彈高度else//中點高度<當前導彈高度a=mid+1;//左區間變為當前導彈高度向后1位}dp[a]=missile[i];//左區間起始高度變為當前導彈高度}}cout<<ans<<endl;//輸出需要多少套系統return 0; }

?

總結

以上是生活随笔為你收集整理的导弹拦截（洛谷-P1020）的全部內容，希望文章能夠幫你解決所遇到的問題。

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