動態規劃 導彈攔截，規劃導彈攔截

動態規劃 導彈攔截，規劃導彈攔截

題意：一種導彈攔截系統的第一發炮彈能夠到達任意的高度，但是以後每一發炮彈都不能高於前一發的高度。某天，雷達捕捉

到敵國的導彈來襲。由於該系統還在試用階段，所以只有一套系統，因此有可能不能攔截所有的導彈。輸入導彈依次飛來的高

度，計算這套系統最多能攔截多少導彈，如果要攔截所有導彈最少要配備多少套這種導彈攔截系統？

 第一問思路非常簡單，不斷改變終止點的位置，更新dp數組。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int dp[1010],a[1010];
int main()
{
    int cases;
    cin>>cases;
    while(cases--)
    {
        memset(dp,0,sizeof(dp));
        int n;
        cin>>n;
        for(int i=0;i<n;i++)
            scanf("%d",&a[i]);
        dp[0]=1;//最小子序列一定是1，沒有更小的了
        for(int i=1;i<n;i++)
        for(int j=0;j<i;j++)
        if(a[i]<a[j]&&dp[j]+1>dp[i]){dp[i]=dp[j]+1;}
        cout<<*max_element(dp,dp+n)<<endl;
    }
}

第二問難度比較大

我們把第二問的問題抽象出來，那就是：把一個數列劃分成最少的最長不升子序列。

Dilworth定理

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int dp[1010],a[1010];
int main()
{
    int cases;
    cin>>cases;
    while(cases--)
    {
        int n;
        cin>>n;
        fill(dp,dp+n,1);
        for(int i=0;i<n;i++)
            scanf("%d",&a[i]);
        dp[0]=1;//最小子序列一定是1，沒有更小的了
        for(int i=1;i<n;i++)
        for(int j=0;j<i;j++)
        if(a[j]<a[i]&&dp[j]+1>dp[i]){dp[i]=dp[j]+1;}//changes;
        cout<<*max_element(dp,dp+n)<<endl;
    }
}

思路就是從頭錄到tail，能摁在一塊的安一快。