某国为了防御敌国的导弹袭击，开发出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都要高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭，并观测到导弹依次飞来的高度，请计算这套系统最多能拦截多少导弹，同时，司令部想知道拦截下来的导弹的高度。拦截来袭导弹时，必须按来袭导弹袭击的时间顺序，不允许先拦截后面的导弹，再拦截前面的导弹。
第一行是一个整数t,代表case数。 对于每一个case，第一行是一个整数n(1≤n≤100000)； 第二行是n个非负整数，表示第n枚导弹的高度，按来袭导弹的袭击时间顺序给出，以空格分隔。数据保证高度不会超过100000.
对于每一个case,第一行输出最多能拦截的导弹数，第二行按来袭顺序输出拦截下来的导弹的高度构成的序列，以一个空格隔开。若有不止一种方法可以拦截最多的导弹，输出字典序最小的。
解题报告:
首先我们令 c[i] 表示长度为 i 的上升子序列中最后一位最小的.可以注意到，c数组是单调不减的，我们每次都可二分求解.
之后我们考虑如何输出答案,从后往前扫，依次匹配长度为 x ,x – 1 , x – 2 ….为结尾的上升子序列，每次需要前面一个数小于后面一个数即可.
#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> #include <stack> using namespace std; const int maxn = 1e5 + 50; int h[maxn],n,c[maxn],maxlength,f[maxn]; stack<int>s; /* 贪心dp c[i] -> 长度为 i 的最长上升子序列中的最小的最后一位 */ int main(int argc,char *argv[]) { int Case; scanf("%d",&Case); c[0] = 0; while(Case--) { memset(c,-1,sizeof(c)); scanf("%d",&n); for(int i = 0 ; i < n ; ++ i ) scanf("%d",h + i); c[1] = h[0] , maxlength = 1 , f[0] = 1; for(int i = 1 ; i < n ; ++ i) { int pos = lower_bound(c+1,c+maxlength+1,h[i]) - c; if (c[pos] == -1 || c[pos] > h[i]) c[pos] = h[i]; f[i] = pos; maxlength = max(maxlength,f[i]); } printf("%d\n",maxlength); int need = maxlength , pre = 1 << 20; for(int i = n - 1 ; i >= 0 ; -- i) //遍历 ,尽可能小 { if (f[i] == need && h[i] < pre) { need--; pre = h[i]; s.push(h[i]); } } printf("%d",s.top());s.pop(); while(!s.empty()) { printf(" %d",s.top()); s.pop(); } printf("\n"); } return 0; }
转载于:https://www.cnblogs.com/Xiper/p/4539652.html
