https://vjudge.net/problem/HDU-1257
    最少拦截系统

    1. //二分做法
    2. #include <cmath>
    3. #include <cstdio>
    4. #include <iostream>
    5. #include <algorithm>
    6. #include <queue>
    7. #include <map>
    8. #include <cstring>
    9. #include <vector>
    10. #include <stack>
    11. #include <string>
    13. using namespace std;
    14. #define ll long long
    15. #define ff first
    16. #define ss second
    17. #define mp make_pair
    18. #define ph push
    19. #define pb push_back
    20. #define all(x) (x).begin(), (x).end()
    21. typedef pair<int, int> pii;
    22. const int N = 3e4 + 5;
    23. const int INF = 1e9 + 5;
    24. priority_queue<int, vector<int>, greater<int> > pq;
    25. int dp[N], a[N];
    27. int main() {
    28.     ios::sync_with_stdio(false);
    29.     int n;
    30.     while (cin >> n) {
    31.         memset(a, 0, sizeof(a));
    32.         for (int i = 0; i < N; i++) {
    33.             dp[i] = INF;
    34.         }
    35.         for (int i = 1; i <= n; ++i) {
    36.             cin >> a[i];
    37.         }
    38.         for (int i = 1; i <= n; i++) {
    39.             *lower_bound(dp, dp + n, a[i]) = a[i];
    40.         }
    41.         cout << (lower_bound(dp, dp + n, INF) - dp) << endl;
    42.     }
    44.     return 0;
    45. }

    1. //dp入门
    2. #include <cmath>
    3. #include <cstdio>
    4. #include <iostream>
    5. #include <algorithm>
    6. #include <queue>
    7. #include <map>
    8. #include <cstring>
    9. #include <vector>
    10. #include <stack>
    11. #include <string>
    13. using namespace std;
    14. #define ll long long
    15. #define ff first
    16. #define ss second
    17. #define mp make_pair
    18. #define ph push
    19. #define pb push_back
    20. #define all(x) (x).begin(), (x).end()
    21. typedef pair<int, int> pii;
    22. const int N = 3e4 + 5;
    23. const int INF = 1e9 + 5;
    24. priority_queue<int, vector<int>, greater<int> > pq;
    25. int dp[N], a[N];
    27. int main() {
    28.     ios::sync_with_stdio(false);
    29.     int n;
    30.     while (cin >> n) {
    31.         int sum=-1;
    32.         memset(a, 0, sizeof(a));
    33.         for (int i = 1; i <= n; ++i) {
    34.             cin >> a[i];
    35.         }
    36.         for (int i = 1; i <= n; i++) {
    37.             //记得初始化，如果有必要
    38.             dp[i]=1;
    39.             for(int j=1;j<i;j++){
    40.                 if(a[j]<a[i]){
    41.                     //dp[j] 是前面的状态
    42.                     dp[i]=max(dp[j]+1,dp[i]);
    43.                 }
    44.             }
    45.             sum=max(sum,dp[i]);
    46.         }
    47.         cout << sum << endl;
    48.     }
    50.     return 0;
    51. }