題目描述

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

輸入格式

輸入數據為兩行，
第一行為導彈的數目N(n<=1000)
第二行導彈依次飛來的高度，所有高度值均為不大于30000的正整數。

輸出格式

輸出只有一行是這套系統最多能攔截的導彈數和要攔截所有導彈最少要配備這種導彈攔截系統的套數。兩個數據之間用一個空格隔開.

樣例輸入

8389 207 155 300 299 170 158 65樣例輸出

6 2

三維狀態圖像

#include<iostream> using namespace std;int max( int a,int b ){ return a>b?a:b; }int main() {int n;int date[1000];int DP1[1000];int count[1000];for( int i=0;i<1000;i++ )date[i]=DP1[i]=count[i]=0;scanf( "%d",&n );for( int i=0;i<n;i++ )scanf( "%d",&date[i] );int ans1=0;for( int i=0;i<n;i++ ){for( int j=0;j<i;j++ )if( date[i]<date[j] )DP1[i]=max(DP1[i],DP1[j]);DP1[i]++;ans1=max( ans1,DP1[i] );//count[DP[i]]++;}int ans2=0;for( int i=0;i<n;i++ ){DP1[i]=0;for( int j=0;j<i;j++ )if( date[i]>date[j] )DP1[i]=max(DP1[i],DP1[j]);DP1[i]++;ans2=max( ans2,DP1[i] );//count[DP[i]]++;}printf( "%d %d\n",ans1,ans2 );return 0; }
第一問很簡單。直接最長降序子序列。
那么第二問怎么辦？開始想了很久沒有想通。我簡單的認為只是在第一問求出的基礎上求出相應DP值的個數最多的那個就是答案了。這么想看上去有道理。因為最高的這么打下來，會消滅很多比他低的，有多少個1就可以發多少枚炮彈，如果剩余了2的話，就以2為起始點放炮。這樣看上去很正確，但是實際上卻是錯的。為什么？因為DP的標號不代表高度。例如DP[I]=2,DP[J]=1;可以說明high[I]>high[J]嗎？不行。既然這樣不成立，那我的那種按DP標號來進行判斷的方式當然不成立了。
舉一個很小的例子，2 5 3 4 這樣我算出來會是2，實際上卻要3枚才能打完。
正確的思路呢？每顆炮彈都要被擊中，比當前點高的又在后面的炮彈就打不中了。這樣就轉化為就最長升序子序列了。

總結

以上是生活随笔為你收集整理的NIOP 1999 导弹问题 最长升降序子序列 DP[小思路]的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。