UESTC_导弹拦截 2015 UESTC Training for Dynamic Programming

N - 导弹拦截

Time Limit: 3000/1000MS (Java/Others)     Memory Limit: 65535/65535KB (Java/Others)
Submit Status

某国为了防御敌国的导弹袭击,开发出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都要高于前一发的高度。某天,雷达捕捉到敌国的导弹来袭,并观测到导弹依次飞来的高度,请计算这套系统最多能拦截多少导弹,同时,司令部想知道拦截下来的导弹的高度。拦截来袭导弹时,必须按来袭导弹袭击的时间顺序,不允许先拦截后面的导弹,再拦截前面的导弹。

Input

第一行是一个整数t,代表case数。 对于每一个case,第一行是一个整数n(1≤n≤100000); 第二行是n个非负整数,表示第n枚导弹的高度,按来袭导弹的袭击时间顺序给出,以空格分隔。数据保证高度不会超过100000.

Output

对于每一个case,第一行输出最多能拦截的导弹数,第二行按来袭顺序输出拦截下来的导弹的高度构成的序列,以一个空格隔开。若有不止一种方法可以拦截最多的导弹,输出字典序最小的。

Sample input and output

Sample Input Sample Output
1
5
1 6 3 5 7
4
1 3 5 7

解题报告:

首先我们令 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 + ;
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[] = ;
while(Case--)
{
memset(c,-,sizeof(c));
scanf("%d",&n);
for(int i = ; i < n ; ++ i ) scanf("%d",h + i);
c[] = h[] , maxlength = , f[] = ;
for(int i = ; i < n ; ++ i)
{
int pos = lower_bound(c+,c+maxlength+,h[i]) - c;
if (c[pos] == - || c[pos] > h[i])
c[pos] = h[i];
f[i] = pos;
maxlength = max(maxlength,f[i]);
}
printf("%d\n",maxlength);
int need = maxlength , pre = << ;
for(int i = n - ; i >= ; -- 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 ;
}
上一篇:Cheatsheet: 2013 07.21 ~ 07.31


下一篇:HTML基础和表格