[問題描述]
某國開發了導彈攔截系統，以防禦敵國的導彈攻擊。但是，這種導彈攔截系統有壹個缺陷:雖然它的第壹發炮彈可以達到任何高度，但未來的每壹發炮彈都不可能高於前壹發。有壹天，雷達發現敵人的導彈來了。因為系統還在試驗階段，只有壹個系統，所以可能無法攔截所有導彈。
依次輸入導彈的飛行高度(雷達給出的高度數據是不大於30000的正整數，每個數據之間至少有壹個空格)，計算出該系統最多可以攔截多少枚導彈，如果要攔截所有導彈，至少要裝備多少套這樣的導彈攔截系統。
[輸入-輸出樣本]
輸入:
389 207 155 300 299 170 158 65
輸出:
6(可攔截的最大導彈數量)
2(攔截所有導彈的最小系統數量)
【問題分析】
先解決第壹個問題。壹個系統可以攔截的最大導彈數量與其最終攔截的導彈高度密切相關。假設a[i]表示當攔截的最後壹枚導彈是第I枚導彈時，系統可以攔截的最大導彈數。比如樣本中的a[5]=3，表示如果系統攔截的最後壹枚導彈是299枚，那麽最多可以攔截第65438枚+第0枚(389)、第4枚(300)、第5枚(299)。顯然，a[1]~a[8]中的最大值就是第壹個問題的答案。關鍵是怎麽找到壹個[1]~壹個[8]。
假設現在已經得到了a[1]~a[7](註:動態編程中往往需要這個假設)，那麽如何求a[8]？A[8]要求系統攔截的最後1枚導彈必須是65枚，也就是說倒數第二枚攔截導彈的高度必須不小於65枚，所以滿足要求的導彈是389、207、155、300、299、170和158。如果最後壹秒導彈是300，那麽A[8]= A[4]+1；如果倒數第二枚導彈是299，那麽A[8]= A[5]+1；同樣，a[8]也可能是a[1]+1，a[2]+1，.當然，我們現在求的是以65結尾的最大導彈數，所以a[8]應該取所有可能值的最大值，即A [8] = Max {A [1]+1，A [2]+1，...，A [7]+65448。
同樣，我們可以假設a[1]~a[6]都已知要找a[7]。同樣，a[6]、a[5]、a[4]、a[3]和a[2]是類似的解，a[1]是1，也就是說，如果系統攔截的最後壹枚導彈是389，那麽只能攔截65438+。
這樣，求解過程可以用下面的公式來概括:
a[1]=1
a[I]= max { a[j]}+1(I & gt；1，j=1，2，…，i-1，j還滿足:a[j]& gt；=a[i])
最後只輸出a[1]~a[8]的最大值。這就是第壹個問題的解決方法，叫做“動態規劃”。
第二個問題更有意思。因為它跟在第壹個問題後面，所以很容易受到前壹個問題的影響。第壹個問題用很多次，然後得出總次數，這是不對的。舉反例不難，比如長度為7的高度序列“7 5 4 1 6 3 2”，最長非升序列“7 5 4 3 2”，多次求最長非升序列的結果是三個系統；但實際上只需要兩盤就可以分別擊落“7 5 4 1”和“6 3 2”。所以不能用“動態規劃”來做。那麽，正確的方法是什麽呢？
我們的目標是用最少的系統數量擊落所有導彈，但如何在系統間分配導彈數量並不重要。以上錯誤的想法是繼承了“壹個系統攔截盡可能多的導彈”的思維定勢，忽略了最優解中各系統攔截數量相對平均的情況。本質上是壹種貪婪算法，但是貪婪策略是錯誤的。如果就各系統攔截的導彈而言都不行，那就換個思路，從攔截某壹枚導彈所選擇的系統入手。
題目告訴我們，現有系統的當前瞄準高度壹定不能低於來襲導彈的瞄準高度，所以當現有系統無法攔截導彈時，不得不啟用新系統。如果現有的某個系統可以攔截導彈，是繼續使用還是另起爐竈？事實是，無論使用哪種系統，只要攔截導彈，系統的瞄準高度就等於導彈高度，新舊系統都適用。新系統可以攔截最高的導彈高度，即新系統的性能優於任何壹套使用過的系統。在這種情況下，我們當然應該選擇現有的制度。如果有多個現有系統可以攔截導彈，我們應該選擇哪壹個？目前瞄準高度高的系統“潛力”更大，瞄準高度低的系統就不壹樣了。它能射的導彈，其他系統也能射，但它射不到的導彈，不壹定是其他系統射不到的。所以當有多個系統可供選擇時，要選擇瞄準高度最低的壹個，當然瞄準高度也要大於等於來襲導彈的高度。
解題時，用壹個數組sys寫下現有系統的當前瞄準高度，數組中實際元素的個數就是第二個問題的答案。
[參考程序]
程序noip 1999 _ 2；
const max = 1000；
var i，j，current，maxlong，minheight，select，tail，total:longint；
最長高度，sys:array [1..max]of longint；
行:字符串；
開始
write('輸入測試數據:')；
readln(行)；{輸入字符串}
I:= 1；
總計:= 0；{進入的導彈數量}
而我& lt= length(line)do {分解幾個數字，存儲在高度數組中}
開始
while(我& lt=length(line))和(line[I]= ' ')do I:= I+1；{過濾空間}
電流:= 0；{記錄導彈的高度}
while(我& lt=length(line))和(line[I]& lt；& gt)do {把字符串變成數字}
開始
current:= current * 10+ord(line[I])-ord(' 0 ')；
i:=i+1
結束；
合計:=合計+1；
高度[總計]:=當前{存儲在高度中}
結束；
最長[1]:= 1；{以下是動態編程的第壹個問題}
對於i:=2到total do
開始
maxlong:= 1；
對於j:=1至i-1 do
開始
如果高度[I]& lt；=高度[j]
那麽如果longest[j]+1 & gt；maxlong
那麽maxlong:= longest[j]+1；
最長[I]:= maxlong {第I枚導彈後可攔截的最大導彈數}
結束；
結束；
maxlong:= longest[1]；
對於i:=2到total do
if longest[I]& gt；maxlong then maxlong:= longest[I]；
writeln(maxlong)；{輸出第壹個問題的結果}
sys[1]:= height[1]；{問下面第二個問題}
尾部:= 1；{數組下標，最後是所需系統的數量}
對於i:=2到total do
開始
min height:= maxint；
對於j:= 1 to tail do {尋找最合適的系統}
if sys[j]& gt；那麽身高[我]
if sys[j]& lt；那就最小吧
begin min height:= sys[j]；select:= j end；
If minheight = maxint {打開新系統}
然後開始tail:= tail+1；sys[tail]:=height[i]結束
else sys[select]:=height[i]
結束；
writeln(尾部)
結束。
[部分測試數據]
輸入1:300 250 275 252 200 138 245。
輸出1:
五
2
輸入2:181 205 471 782 1033 1058 111。
產出2:
1
七
輸入3:465 978 486 476 324 575 384 278 214 657 218 445 123。
產出3:
七
四
輸入4:236 865 858 565 545 455 656 844 735 638 652 659 714 845。
產出4:
六
七
夠詳細嗎？