藍橋杯算法訓練——攔截飛彈

試題 算法訓練 攔截飛彈

資源限制

時間限制：1.0s 記憶體限制：256.0MB

問題描述

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

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

輸入格式

　　一行，為飛彈依次飛來的高度

輸出格式

　　兩行，分别是最多能攔截的飛彈數與要攔截所有飛彈最少要配備的系統數

樣例輸入

389 207 155 300 299 170 158 65

樣例輸出

6

2

一個比較好做的動态規劃題目，要計算這套系統最多能夠攔截多少飛彈，其實就是要找出所給飛彈高度這些數的最長遞降序列長度，而計算攔截所有飛彈最少要配備攔截系統套數，則是要找出這些數的最長遞增序列長度。這裡的序列可以是不連續的。

下面是解決這個問題的核心步驟：

用數組s來存儲這些飛彈高度，兩重循環，每次循環篩選出最長的遞增和遞降序列長度，

當s[j]>s[i]，dp[i]=max(dp[i],dp[j]+1)注（j<i），dp[i]表示以第i個飛彈高度為終點的遞降序列長度，

當s[j]<s[i]，dp2[i]=max(dp2[i],dp2[j]+1)注（j<i），dp2[i]表示以第i個飛彈高度為終點的遞增序列長度

#include<bits/stdc++.h>//c++萬能頭檔案，包含了大部分c和c++的頭檔案，不過有些評測系統不能用
using namespace std;

int main()
{
    int n=0,i=0,j,Max1=0,Max2=0,s[100],dp1[100]={0},dp2[100]={0};
    while(cin>>s[i])
    {
        i++;
        n++;
    }
    for(i=0;i<n;i++)
    {
        dp1[i]=1;
        dp2[i]=1;
        for(j=0;j<i;j++)
        {
            if(s[j]>s[i])//遞降序列
                dp1[i]=max(dp1[i],dp1[j]+1);
            else//遞增序列
                dp2[i]=max(dp2[i],dp2[j]+1);
        }
        //找到最長的遞增和遞降序列
        Max1=max(dp1[i],Max1);
        Max2=max(dp2[i],Max2);
    }
    cout<<Max1<<"\n"<<Max2;
}