【例4】攔截×××(《資訊學奧賽一本通》)

/*

【例4】攔截×××

(Noip1999提高組第1題--DP+貪心)

https://www.luogu.org/problemnew/show/P1020

https://www.luogu.org/problemnew/show/P1158

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

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

樣例：

INPUT

389 207 155 300 299 170 158 65

int i,j,k,x,n,maxx,m,a[10000],b[10000],h[10000];

i=1;
n=0;
m=0;

memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
memset(h,0,sizeof(h));

while (cin>>a[i])
{
    maxx=0;
    //計算前i-1個×××最佳攔截的方案
    for (j=1;j<=i-1;j++)   
    {
        if (a[j]>=a[i])
        if (b[j]>maxx)
            maxx=b[j];
    }             

    b[i]=maxx+1;

    if (b[i]>m) m=b[i];

    x=0;
    //計算由哪一套系統攔截×××
    for (k=1;k<=n;k++)                 
        if (h[k]>=a[i]) 
        if (x==0) x=k;
        //如果有多套系統可攔截，則選擇上一次攔截高度最低的
        else if (h[k]<h[x]) x=k;         

    //新增一套×××攔截系統
    if (x==0) 
    {
        n++;
        x=n;
    }                

    h[x]=a[i];

    i++;
} 
cout<<m<<endl<<n<<endl;