「CF10D」LCIS

传送门

Luogu

解题思路

首先考虑怎么求方案，这样才可能会输出方案。

考虑 \(\text{DP}\)。

设 \(f[i][j]\) 表示在 \(a\) 序列中选择一个 \([1...i]\) 的子序列与子序列 \(b[1...j]\) 匹配得到的最长LCIS（其中 \(b[j]\) 强制被选）。

有一个很显然的 \(O(n^3)\) 转移：

当 \(a_i = b_j\) 时：\(f[i][j] = \max\limits_{1\le k < j \text{且} b_k < b_j}\left\{f[i - 1][k] + 1\right\}\)

当 \(a_i \neq b_j\) 时：\(f[i][j] = f[i - 1][j]\)

这样子转移显然是没错的，但要是 \(1\le N \le 10^3\) 呢？

其实转移可以做到 \(O(n^2)\) 。

仔细想一想就可以发现这样做的转移是具有决策单调性的，我们每次进行第一种转移时，决策集合总是不断扩大的，我们大可不必每次都扫一遍取 \(\max\) 只要动态的维护一下决策集合中的最优决策点就好了。

然后再考虑输出方案。

我们设一个和 \(f\) 数组并存的 \(p\) 数组，每次成功转移时就更新一下 \(p\) ,最后就顺着 \(p\) 数组往前跳倒序输出就好了。

细节注意事项

咕咕咕

参考代码

#include <algorithm>

#include <iostream>

#include <cstring>

#include <cstdlib>

#include <cstdio>

#include <cctype>

#include <cmath>

#include <ctime>

#define rg register

using namespace std;

template < typename T > inline void read(T& s) {

 	s = 0; int f = 0; char c = getchar();

 	while (!isdigit(c)) f |= (c == '-'), c = getchar();

 	while (isdigit(c)) s = s * 10 + (c ^ 48), c = getchar();

 	s = f ? -s : s;

}

const int _ = 500 + 10;

int n, m, a[_], b[_];

int f[_][_], p[_][_];

inline void print(int id)

{ if (id) print(p[n][id]), printf("%d ", b[id]); }

int main() {

#ifndef ONLINE_JUDGE

	freopen("in.in", "r", stdin);

#endif

	read(n); for (rg int i = 1; i <= n; ++i) read(a[i]);

	read(m); for (rg int i = 1; i <= m; ++i) read(b[i]);

	a[0] = b[0] = -1;

	for (rg int i = 1; i <= n; ++i)

		for (rg int j = 1; j <= m; ++j) {

			if (a[i] != b[j]) {

				f[i][j] = f[i - 1][j], p[i][j] = p[i - 1][j];

			} else {

				for (rg int k = 0; k < j; ++k)

					if (f[i][j] < f[i - 1][k] + 1 && b[k] < b[j])

						f[i][j] = f[i - 1][k] + 1, p[i][j] = k;

			}

		}

	int id = 0, _max = 0;

	for (rg int i = 1; i <= m; ++i)

		if (_max < f[n][i])

			_max = f[n][i], id = i;

	printf("%d\n", _max), print(id);

	return 0;

}

完结撒花 \(qwq\)

巴特西

「CF10D」LCIS

解题思路

细节注意事项

参考代码

最新文章

热门文章