题目大意：一种拦截导弹能拦截多枚导弹，但是它在每次拦截后高度不会再升高，给出导弹的序列，问最多能拦截多少枚导弹？
最长递减子序列问题。
1 #include <cstdio> 2 #include <vector> 3 #include <algorithm> 4 using namespace std; 5 6 vector<int> m, lds; 7 8 int main() 9 { 10 #ifdef LOCAL 11 freopen("in", "r", stdin); 12 #endif 13 int x, kase = 0; 14 while (scanf("%d", &x) != EOF && x != -1) 15 { 16 kase++; 17 m.clear(); 18 m.push_back(x); 19 while (scanf("%d", &x) && x != -1) 20 m.push_back(x); 21 lds.clear(); 22 lds.resize(m.size(), 1); 23 for (int i = 1; i < m.size(); i++) 24 { 25 for (int j = 0; j < i; j++) 26 if (m[i] < m[j] && lds[j]+1 > lds[i]) 27 lds[i] = lds[j] + 1; 28 } 29 int ans = 1; 30 for (int i = 0; i < lds.size(); i++) 31 ans = max(ans, lds[i]); 32 if (kase > 1) printf(" "); 33 printf("Test #%d: maximum possible interceptions: %d ", kase, ans); 34 } 35 return 0; 36 }