HDU 1257 最少拦截系统

传送门：http://acm.hdu.edu.cn/showproblem.php?pid=1257

解题思路：

dp[i]:编号为i+1的导弹能飞的最高的高度。

很明显dp数组是单调递增的数列。

在拦截第j发炮弹的时候，如果a[j]大于已经安装的系统最高的高度，明显在增加一套系统，

而若小于已经安装系统的最大高度，明显不需要安装一台系统，只需要更新dp数组中dp[k]>=a[j]（0<k<=i)其k是满足条件的最小值。

实现代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAXN=1000000;
const int INF=1<<30;
int a[MAXN];
int dp[MAXN];

/************************************
dp[i]:表示编号为i+1的导弹能打的最大高度。
**************************************/
int main(){
    int n;
    while(scanf("%d",&n)!=EOF){
        for(int i=0;i<n;i++)
            scanf("%d",&a[i]);
        fill(dp,dp+n,INF);

        for(int i=0;i<n;i++)
            *lower_bound(dp,dp+n,a[i])=a[i];
        printf("%d
",lower_bound(dp,dp+n,INF)-dp);
    }
}