×××攔截與動态規劃

       某國為了防禦敵國的×××襲擊，發展出一種×××攔截系統。但是這種×××攔截系統有一個缺陷：

雖然它的第一發炮彈能夠達到任意的高度，但是以後每一發炮彈都不能高于前一發的高度。某天，

雷達捕捉到敵國的×××來襲。由于該系統還在使用階段，是以隻有一套系統，是以有可能不能攔截所有的×××。

輸入×××依次飛來的高度（雷達給出高度資料是不大于30000的正整數），計算這套系統最多能攔截多少×××，

如果要攔截所有×××最少要配備多少套這種×××系統。

樣例：

  Input:   389   207     155     300     299     170     158     65

Output:   6(最多攔截×××數)

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

很早就看到這個經典的題目，但是一直沒有把它的代碼出來。一開始的思路是動态規劃，步步最優結果最優。開始，我嘗試着從後面倒序計算，因為後面的計算要用到前面的結果，是以用數組存儲從後面計算的結果，結果越寫到後面感覺越亂，越寫越複雜。最後還是順着我的思路寫完了。

後來我上網一查才知道，設計的算法不合理，沒有充分了解動态規劃的解決問題的思想。然後。。。重新認真的分析，參考。。。才明白，子問題和原問題的解間有聯系，隻需要解決子問題，最後再累加，就問得到原問題的解。。。。

應該好好去了解動态規劃。。。

#include <iostream>

using namespace std;

const int MAX = 20;

bool prove(int arr[]);

void solution(int arr[],int *a,int *b);   //a為攔截數,b為需要裝置數