攔截導彈問題

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

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

樣例：

INPUT

389 207 155 300 299 170 158 65

OUTPUT

6（最多能攔截的導彈數）

389 300 299 170 158 65

 1 // the solution of the missile
 2 // use the DP(dynamic process) algorithms
 3 #include<iostream>
 4 
 5 #define MAX 100//define the missile max total number
 6 using namespace std;
 7 
 8 void calc(int a[],int i)
 9 {
10     int b[MAX];
11     b[0]=a[0];
12     int ptr=0;
13     int m,k;
14 
15     for( k=1;k<i;k++)
16     {
17         
18           if(a[k]<=b[ptr])//加入數組末尾,非遞減序列
19             {
20                 ptr++;
21                 b[ptr]=a[k];
22             
23             }
24             else//將a[k]放入數組B的正確位置
25             {
26                 for(int n=0;n<=ptr;n++)
27                 {
28                     if(a[k]>b[n])
29                     {
30                         b[n]=a[k];
31                         break;
32                     }
33                 }
34                 
35             }
36 
37     
38     }
39     cout<<"the total number of the missile is:"<<ptr+1<<endl;
40     for(k=0;k<=ptr;k++)
41         cout<<b[k]<<" ";
42    
43 
44 }
45 
46 int main()
47 {
48     int arr[MAX]={0};
49     int i;
50     cout<<"Input the total missile number:";
51     cin>>i;
52     int k=0;
53     while(i>0)
54     {
55         cin>>arr[k];
56         k++;
57         i--;
58     }
59     calc(arr,k);
60     return 0;
61 }

運行結果: