题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1257
分析：对于每一个位置（i)，向前找是否存在比它小（或者相等的数）记为j，如果存在，那i必然相较与j得多开一个拦截系统；
1 #include<iostream> 2 #include<sstream> 3 #include<cstdio> 4 #include<cstdlib> 5 #include<string> 6 #include<cstring> 7 #include<algorithm> 8 #include<functional> 9 #include<iomanip> 10 #include<numeric> 11 #include<cmath> 12 #include<queue> 13 #include<vector> 14 #include<set> 15 #include<cctype> 16 #define PI acos(-1.0) 17 const int INF = 0x3f3f3f3f; 18 const int NINF = -INF - 1; 19 const int maxn = 3e4 + 5; 20 typedef long long ll; 21 using namespace std; 22 int a[maxn], dp[maxn]; 23 int main() 24 { 25 int n; 26 while (scanf("%d", &n) != EOF) 27 { 28 int ans = 0; 29 for (int i = 0; i < n; ++i) 30 scanf("%d", &a[i]); 31 for (int i = 0; i < n; ++i) dp[i] = 1; 32 for (int i = 0; i < n; ++i) 33 { 34 for (int j = 0; j < i; ++j) 35 { 36 if (a[j] <= a[i]) 37 dp[i] = max(dp[j] + 1, dp[i]); 38 } 39 ans = (max(ans, dp[i])); 40 } 41 //for (int i = 0; i < n; ++i) cout << dp[i] << ' '; 42 //cout << endl; 43 printf("%d ", ans); 44 } 45 return 0; 46 }