现在的位置: 首页 > 综合 > 正文

1046: [HAOI2007]上升序列 (动态规划+二分)

2017年11月16日 ⁄ 综合 ⁄ 共 772字 ⁄ 字号 评论关闭
#include<bits/stdc++.h>
using namespace std;
inline int read(){
	int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
const int maxn=100001;
int n,m,cnt,a[maxn],best[maxn],f[maxn];
inline int find(int x){
	int l=1,r=cnt,ans=0;
	while(l<=r){
		int mid=(l+r)>>1;
		if(best[mid]>x)ans=mid,l=mid+1;
		else r=mid-1;
	}
	return ans;
}
inline void solve(int x){
	int last=0;
	for(int i=1;i<=n;i++)
		if(f[i]>=x&&a[i]>last){
			printf("%d",a[i]);
			if(x!=1)printf(" ");
			last=a[i];
			x--;
			if(!x)break;
		}
	printf("\n");
}
int main(){
	n=read();
	for(int i=1;i<=n;i++)
		a[i]=read();
	for(int i=n;i;i--){
		int t=find(a[i]);
		f[i]=t+1;
		cnt=max(cnt,t+1);
		if(best[t+1]<a[i])
			best[t+1]=a[i];
	}
	m=read();
	for(int i=1;i<=m;i++){
		int x=read();
		if(x<=cnt)solve(x);
		else puts("Impossible");
	}
	return 0;
}

抱歉!评论已关闭.