I – 最少拦截系统Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64uSubmit Status Practice HDU 1257Description某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统.但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能超过前一发的高度.某天,雷达捕捉到敌国的导弹来袭.由于该系统还在试用阶段,所以只有一套系统,因此有可能不能拦截所有的导弹.怎么办呢?多搞几套系统呗!你说说倒蛮容易,成本呢?成本是个大问题啊.所以俺就到这里来求救了,请帮助计算一下最少需要多少套拦截系统.Input输入若干组数据.每组数据包括:导弹总个数(正整数),导弹依此飞来的高度(雷达给出的高度数据是不大于30000的正整数,用空格分隔)Output对应每组数据输出拦截所有导弹最少要配备多少套这种导弹拦截系统.Sample Input8 389 207 155 300 299 170 158 65 Sample Output
2
拦截高度是递减的，，所以是求最长上升子序列
#include<bits/stdc++.h>using namespace std;template<class T>inline T read(T&x){char c;while((c=getchar())<=32)if(c==EOF)return 0;bool ok=false;if(c=='-')ok=true,c=getchar();for(x=0; c>32; c=getchar())x=x*10+c-'0';if(ok)x=-x;return 1;}template<class T> inline T read_(T&x,T&y){return read(x)&&read(y);}template<class T> inline T read__(T&x,T&y,T&z){return read(x)&&read(y)&&read(z);}template<class T> inline void write(T x){if(x<0)putchar('-'),x=-x;if(x<10)putchar(x+'0');else write(x/10),putchar(x%10+'0');}template<class T>inline void writeln(T x){write(x);putchar('\n');}//——-ZCC IO template——const int maxn=1e5+1000;const double inf=999999999;#define lson (rt<<1),L,M#define rson (rt<<1|1),M+1,R#define M ((L+R)>>1)#define For(i,t,n) for(int i=(t);i<(n);i++)typedef long long LL;typedef double DB;typedef pair<int,int> P;#define bug printf("—\n");#define mod 100007int a[maxn];int dp[maxn];int main(){int n,E,F;while(read(n)){for(int i=0;i<n;i++)read(a[i]);fill(dp,dp+n,inf);for(int i=0;i<n;i++){*lower_bound(dp,dp+n,a[i])=a[i];}writeln(lower_bound(dp,dp+n,inf)-dp);}return 0;}
转动心中的期待，血在澎湃，吃苦流汗算什么。
