攔截導彈
動態規劃問題
某國為了防御敵國的導彈襲擊，發展出一種導彈攔截系統。但是這種導彈攔截系統有一個缺陷：雖然它的第一發炮彈能夠到達任意的高度，但是以後每一發炮彈都不能高於前一發的高度。某天，雷達捕捉到敵國的導彈來襲。由於該系統還在試用階段，所以只有一套系統，因此有可能不能攔截所有的導彈。
輸入導彈依次飛來的高度（雷達給出的高度數據是不大於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 }
運行結果:
