NC19965. [HAOI2007]上升序列
描述
输入描述
第一行一个N，表示序列一共有N个元素第二行N个数，为a1,a2,…,an第三行一个M，表示询问次数。下面接M行每行一个数L，表示要询问长度为L的上升序列。N ≤ 10000，M ≤ 1000
输出描述
对于每个询问，如果对应的序列存在，则输出，否则打印Impossible.
示例1
输入:
6 3 4 1 2 3 6 3 6 4 5
输出:
Impossible 1 2 3 6 Impossible
C++11(clang++ 3.9) 解法, 执行用时: 302ms, 内存消耗: 9316K, 提交时间: 2020-03-28 23:47:48
#include<bits/stdc++.h>
using namespace std;
const int MAXN=10005;
int n,m,a[MAXN],dp[MAXN];
int Max;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]),dp[i]=1;
for(int i=n-1;i;i--)
{
Max=1;
for(int j=i+1;j<=n;j++)
if(a[j]>a[i]&&dp[j]+1>Max)
Max=dp[j]+1;
dp[i]=Max;
}
Max=0;
for(int i=1;i<=n;i++)
Max=max(dp[i],Max);
scanf("%d",&m);
for(int i=1;i<=m;i++)
{
int x;
scanf("%d",&x);
if(x>Max)
cout<<"Impossible"<<endl;
else
{
int k=0;
for(int j=1;j<=n;j++)
if(dp[j]>=x&&a[j]>a[k])
{
printf("%d ",a[j]);
k=j;
x--;
if(x==0) break;
}
printf("\n");
}
}
return 0;
}