dp——導彈攔截

 1 /*
 2     導彈攔截問題（也稱為最長不上升子序列問題）是動態規劃中的經典問題之一。問題的描述如下：
 3     給定一個導彈飛行高度的序列，要求攔截所有導彈。攔截系統有一個限制：每次攔截的導彈高度不
 4     能高于前一次攔截的導彈高度。問最少需要多少套攔截系統才能攔截所有導彈，或者一套攔截系統最多能攔截多少導彈。
 5     這個問題可以轉化為兩個子問題：
 6 
 7     1. 最少需要多少套攔截系統：即求導彈高度序列的最長上升子序列（LIS）的長度。
 8     2. 一套攔截系統最多能攔截多少導彈：即求導彈高度序列的最長不上升子序列（LNIS）的長度。
 9     
10     示例數據：{189, 207, 155, 200, 99}
11     
12 */

#include <vector>
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;

int maxMissiles(vector<int>& heights){
    int n = heights.size();
    vector<int> dp(n,1);//dp[i]是當前高度最大不上升子序列的長度
    for(int i=1;i<n;i++){
        for(int j=0;j<i;j++){
            if(heights[j]>=heights[i]){
                dp[i]=max(dp[j]+1,dp[i]);
            }
        }
    }//到這里，dp就已經得到了所有以當前高度值結尾的最大不上升子序列的值
    return *max_element(dp.begin(),dp.end());
}
int maxSystem(vector<int>& heights){
    int n = heights.size();
    vector<int> dp(n,1);
    for(int i = 1;i < n;i++){
        for(int j = 0;j < i;j++){
            if(heights[j]<=heights[i]){
                dp[i]=max(dp[j]+1,dp[i]);
            }
        }
    }

    return *max_element(dp.begin(),dp.end());
}
int main(void){
    vector<int> heights={189,207,155,200,99,50};
    int n = maxMissiles(heights);
    int m = maxSystem(heights);
    printf("最大攔截導彈的個數為:%d\n需要的系統個數:%d",n,m);
    return 0;
}

posted on 2025-03-30 16:01 FYJUN2077 閱讀(17) 評論(0) 收藏舉報

刷新頁面返回頂部