hdu1257 最少拦截系统

题目大意

拦截导弹，每次拦截的高度不能大于上一次，对于给定序列需要几套拦截系统

题解

简单的。。最长上升子序列。。懒得加二分优化了。。数据量太水了导致优不优化。。差别不大

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int dp[30030];
const int MAXN=0x3f3f3f3f;
int main(){
    int n;
    while(~scanf("%d",&n)){
        memset(dp,MAXN,sizeof(dp));
        int res=0,last=0,tmp;
        for(int i=0;i<n;++i){
            scanf("%d",&tmp);
            int j=0;
            while(dp[j]<tmp){
                ++j;
            }
            dp[j]=tmp;
        }
        for(res=0;res<n;++res){
            if(dp[res]!=MAXN){
                continue;
            }
            break;
        }
        printf("%d\n",res);
    }
    return 0;
}