bzoj 1046: [HAOI2007]上升序列 （DP）

题目描述

传送门

题解

最长上升子序列，从后向前推， f[i] 表示的是以位置i开头的最长上升子序列的长度。 至于字典序最小，从前向后扫即可。

代码

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define N 10003 using namespace std; int n,m,f[N],a[N]; void print(int x) { int l=x; int last=0; for (int i=1;i<=n;i++) if (f[i]>=l&&a[i]>last){ l--; last=a[i]; if (l) printf("%d ",a[i]); else { printf("%d\n",a[i]); break; } } } int main() { freopen("a.in","r",stdin); scanf("%d",&n); for (int i=1;i<=n;i++) scanf("%d",&a[i]); f[n]=1; for (int i=n-1;i>=1;i--) { for (int j=i+1;j<=n;j++) if (a[j]>a[i]&&f[j]>f[i]) f[i]=f[j]; f[i]++; } int ans=0; for (int i=1;i<=n;i++) ans=max(ans,f[i]); scanf("%d",&m); for (int i=1;i<=m;i++) { int x; scanf("%d",&x); if (x>ans) printf("Impossible\n"); print(x); } }