用動態規劃實現導彈攔截

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

　　輸入導彈依次飛來的高度(雷達給出的高度數據是不大于30000的正整數)，計算這套系統最多能攔截多少導彈，并依次輸出被攔截的導彈飛來時候的高度。

　　SAMPLE INPUT:

　　389 207 155 300 299 170 158 65

　　SAMPLE OUTPUT:

　　6

　　389 300 299 170 158 65

　　因為只有一套導彈攔截系統，并且這套系統除了第一發炮彈能到達任意高度外，以后的每一發炮彈都不能高于前一發炮彈的高度;所以，被攔截的導彈應該按飛來的 高度組成一個非遞增序列。題目要求我們計算這套系統最多能攔截的導彈數，并依次輸出被攔截導彈的高度，實際上就是要求我們在導彈依次飛來的高度序列中尋找 一個最長非遞增子序列。

　　設 X={x 1 ,x 2 ,…,x n } 為依次飛來的導彈序列， Y={y 1 ,y 2 ,…,y k } 為問題的最優解(即 X 的最長非遞增子序列)， s 為問題的狀態(表示導彈攔截系統當前發送炮彈能夠到達的最大高度，初值為 s=∞—— 第一發炮彈能夠到達任意的高度)。如果 y 1 =x 1 ，即飛來的第一枚導彈被成功攔截。那么，根據題意“每一發炮彈都不能高于前一發的高度”，問題的狀態將由 s=∞ 變成 s≤x 1 ( x 1 為第一枚導彈的高度);在當前狀態下，序列 Y 1 ={y 2 ,…,y k } 也應該是序列 X 1 ={x 2 ,…,x n } 的最長非遞增子序列(大家用反證法很容易證明)。也就是說，在當前狀態 s≤x 1 下，問題的最優解 Y 所包含的子問題(序列 X 1 )的解(序列 Y 1 )也是最優的。這就是攔截導彈問題的最優子結構性質。

　　設 D(i) 為第 i 枚導彈被攔截之后，這套系統最多還能攔截的導彈數(包含被攔截的第 i 枚)。我們可以設想，當系統攔截了第 k 枚導彈 x k ，而 x k 又是序列 X={x 1 ,x 2 ,…,x n } 中的最小值，即第 k 枚導彈為所有飛來的導彈中高度最低的，則有 D(k)=1 ;當系統攔截了最后一枚導彈 x n ，那么，系統最多也只能攔截這一枚導彈了，即 D(n)=1 ;其它情況下，也應該有 D(i)≥1 。

　　假設系統最多能攔截的導彈數為 dmax (即問題的最優值)，則 dmax = max(D(i))

　　2011計算機等級二級C語言五套模擬試題及答案

　　計算機等級考試二級C語言歷年真題匯總(2005-2010)

　　2011年計算機等級考試二級C語言常見問題匯總

　　計算機等級考試二級C語言常見知識點總結