某國為了防御敵國的導彈襲擊，發展中一種導彈攔截系統。但是這種導彈攔截系統有一個缺陷：雖然它的第一發炮彈能夠到達任意的高度，但是以後每一發炮彈都不能高於等於前一發的高度。某天，雷達捕捉到敵國導彈來襲。由於該系統還在試用階段，所以只用一套系統，因此有可能不能攔截所有的導彈。
2 8 389 207 155 300 299 170 158 65 3 88 34 65
6 2
這題數據比較小，每組最多有20個數，可以用dfs，不會超時，但是我感覺用動規更省時，也更好寫代碼可以說是動規入門題
第一次交的時候因為沒有看到不能等於前面的，於是就錯了。1 #include <iostream>
2 #include <cmath>
3 #include <algorithm>
4 using namespace std;
5
6 int main()
7 {
8 int n,m,a[25],b[25];//a數組記錄高度，b數組記錄一第i個數結尾的最大降序序列
9 cin>>n;
10 while (n--)
11 {
12 cin>>m;
13 for (int i=1;i<=m;i++)//輸入數據
14 {
15 cin>>a[i];
16 b[i]=1;//默認以每一個數結尾的最大降序數為1，後面再進行更新
17 }
18 int max=0;
19 for (int i=2;i<=m;i++)
20 {
21 for (int j=1;j<i;j++)
22 {
23 if (a[i]<a[j])//如果第i個數比在它前面的第j個數小，進行判斷，取大的
24 {
25 if (b[i]<b[j]+1)
26 b[i]=b[j]+1;
27 }
28 }
29 if (b[i]>max)
30 max=b[i];
31 }
32 cout <<max<<endl;
33 }
34 return 0;
35 }View Code
