NOIP1999提高組 攔截導彈 missile 解題報告

【題目描述】

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

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

【輸入輸出格式】：

輸入文件

只有一行，有n個整數，中間用一個空格隔開，表示n枚導彈的高度，

輸出文件

有兩行，每行一個數

第一行的整數表示一套系統最多攔截的導彈數量

第二行的整數表示攔截所有導彈最少要配備的導彈攔截系統數量

【輸入輸出樣例】：

missile.in

389 207 155 300 299 170 158 65

missile.out

6（最多能攔截的導彈數）

2（要攔截所有導彈最少要配備的系統數）

【分析】

最長不上升子序列問題，動態規劃。

一遍一遍的進行DP，即求最長不上升子序列，然後每次把最長不上升子序列中的每個數刪除，接著再對剩下的數進行DP～

知道n=0為止～輸出次數即可。

【我的代碼】

#include <iostream>
#include <cstdio>
#define max(a,b) ((a)>(b)?(a):(b))
using namespace std; int num[100000][3]; int n,maxn,maxx; int i,j,k;
void init() {
    int a;
    cin>>a;
    n=0;
    while(cin>>num[n][0])
    {
        num[n][1]=1;
        num[n][2]=0;
        n++;
    }  }
void search() {
    for (i=n-2;i>=0;i--)
    {
        maxn=1;
        for (j=n-1;j>i;j--)
        {
            if (num[i][0]>=num[j][0] && num[j][1]+1>=maxn)
            {
                maxn=num[j][1]+1;
                maxx=j;
            }
        }
        num[i][1]=maxn;
        num[i][2]=maxx;        
    } }
void recover() {
    int newer[10000];
    int top=0;
    for (int i=0;i<n;i++)
    {
        if(num[i][0]!=-1)
        {
            newer[top]=num[i][0];
            top++;
        }
    }
    n=top;
    for (int i=0;i<n;i++)
    {
        num[i][0]=newer[i];
        num[1][1]=1;
        num[1][2]=0;
    } }
void turnto1(int m1,int m2) {
    if (m2<=maxn)
    {
        num[m1][0]=-1;
            turnto1(num[m1][2],m2+1);
    } }

void output() {
    maxn=1,maxx=0;
    for(i=0;i<n;i++)
    {
        if (num[i][1]>maxn)
        {
            maxn=num[i][1];
            maxx=i;
        }
    }
    cout<<maxn<<endl;
    turnto1(maxx,1); }

  int main() {
    freopen("missile.in","r",stdin);
    freopen("missile.out","w",stdout);
    init();
    search();
        output();
    int s=1;
    while(n>0) 
    {
        recover();
        search();
        maxn=1,maxx=0;
        for(i=0;i<n;i++)
        {
            if (num[i][1]>maxn)
            {
                maxn=num[i][1];
                maxx=i;
            }
        }
        turnto1(maxx,1);
        s++;
    }
    cout<<s-1<<endl;
    return 0; }