【BZOJ1046】[HAOI2007]上升序列

题面

bzoj

洛谷

题解

\(dp\)完之后随便搞一下即可，注意不要看错题

代码

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <vector>

using namespace std;

inline int gi() {

	register int data = 0, w = 1;

	register char ch = 0;

	while (!isdigit(ch) && ch != '-') ch = getchar();

	if (ch == '-') w = -1, ch = getchar();

	while (isdigit(ch)) data = 10 * data + ch - '0', ch = getchar();

	return w * data;

}

const int MAX_N = 1e4 + 5;

int N, a[MAX_N], dp[MAX_N];

int main () {

	N = gi(); for (int i = 1; i <= N; i++) a[i] = gi();

	reverse(&a[1], &a[N + 1]);

	fill(&dp[1], &dp[N + 1], 1);

	for (int i = 1; i <= N; i++)

		for (int j = 1; j < i; j++)

			if (a[j] > a[i]) dp[i] = max(dp[i], dp[j] + 1);

	int mx = 1;

	for (int i = 1; i <= N; i++) mx = max(mx, dp[i]);

	int M = gi();

	while (M--) {

		int l = gi();

		if (l > mx) { puts("Impossible"); continue; }

		else {

			int now = 0;

			for (int i = N; i >= 1; i--)

				if (dp[i] >= l && a[i] > now) {

					printf("%d ", a[i]);

					now = a[i], --l;

					if (!l) break;

				}

			printf("\n");

		}

	}

	return 0;

}