HDU 1257——最少拦截系统——————【LIS变型题】

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5;
int a[maxn],dp[maxn];
int main(){
    int n;
    while(scanf("%d",&n)!=EOF){
        for(int i = 1; i <= n; i++){
            scanf("%d",&a[i]);
            dp[i] = 1;
        }
        for(int i = 1; i <= n; i++){
            for(int j = 1; j < i; j++){
                if(a[j] <= a[i]){
                    dp[i] = max(dp[i],dp[j] +1);
                }
            }
        }
        int ans = 0;
        for(int i = 1; i <= n; i++){
            //printf("%d ",dp[i]);
            ans = max(ans,dp[i]);
        }
        printf("%d\n",ans);
    }
    return 0;
}