某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。
输入导弹依次飞来的高度（雷达给出的高度数据是\le 50000≤50000的正整数），计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。
11行，若干个整数（个数\le 100000≤100000）
22行，每行一个整数，第一个数字表示这套系统最多能拦截多少导弹，第二个数字表示如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。
求一个最长严格单调递增子序列和最长不严格单调递减子序列。
读入很毒瘤
#include<bits/stdc++.h> using namespace std; const int maxn=5e5+100; int a[maxn]; int r[maxn]; int l[maxn]; int c[maxn]; int lowbit(int x) { return x&-x; } void update (int x,int v) { for (int i=x;i<maxn;i+=lowbit(i)) c[i]=max(c[i],v); } int getMax (int x) { int ans=0; for (int i=x;i;i-=lowbit(i)) ans=max(ans,c[i]); return ans; } int main () { int n; while (cin>>a[++n]); n--; int pre=0,u=1; int ans=0; for (int i=n;i>=1;i--) { r[i]=getMax(a[i])+1; update(a[i],r[i]); } int Max=0; for (int i=1;i<=n;i++) Max=max(Max,r[i]); memset(c,0,sizeof(c)); for (int i=1;i<=n;i++) { l[i]=getMax(a[i]-1)+1; update(a[i],l[i]); } for (int i=1;i<=n;i++) ans=max(ans,l[i]); printf("%d\n%d\n",Max,ans); }
原文：https://www.cnblogs.com/zhanglichen/p/13455153.html