题目

给定两个整数序列 $A$ 和 $B$ ，长度分别为 $n$ 和 $m$ ，且满足 $1\leq A_i,B_i\leq k$ 。现在你希望求出一个满足 $1\leq C_i\leq k$ 的整数序列 $C$ ，它既不是 $A$ 的子序列，也不是 $B$ 的子序列。求 $C$ 的最小长度。

题解

设 $f_{i,j}$ 表示扫完 $A_i,B_j$ 时 $C$ 的最小长度。

看上去是 $\mathcal{O}(nmk)$ 实际上 $\mathcal{O}(nm)$ 。

代码

const int N = 4010;

inline ll Read() {
	ll x = 0, f = 1;
	char c = getchar();
	while (c != '-' && (c < '0' || c > '9')) c = getchar();
	if (c == '-') f = -f, c = getchar();
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
	return x * f;
}

namespace Main {
	int n, m, K;
	int a[N], b[N];
	int f[N][N], nxta[N][N], nxtb[N][N];
	int main () {
		n = Read(), m = Read(), K = Read();
		for (int i = 1; i <= n; i++) a[i] = Read();
		for (int i = 1; i <= K; i++) nxta[n + 1][i] = n + 1;
		for (int i = n; i >= 0; i--) {
			for (int j = 1; j <= K; j++) nxta[i][j] = nxta[i + 1][j];
			nxta[i][a[i + 1]] = i + 1;
		}
		for (int i = 1; i <= m; i++) b[i] = Read();
		for (int i = 1; i <= K; i++) nxtb[m + 1][i] = m + 1;
		for (int i = m; i >= 0; i--) {
			for (int j = 1; j <= K; j++) nxtb[i][j] = nxtb[i + 1][j];
			nxtb[i][b[i + 1]] = i + 1;
		}
		memset (f, 127 / 3, sizeof f);
		int inf = f[0][0];
		f[0][0] = 0;
		for (int i = 0; i <= n + 1; ++i)
			for (int j = 0; j <= m + 1; ++j) 
				if(f[i][j] < inf)
					for (int k = 1; k <= K; k++) {
						if(nxta[i][k] && nxtb[j][k])
							f[nxta[i][k]][nxtb[j][k]] = min(f[nxta[i][k]][nxtb[j][k]], f[i][j] + 1);
					}
		printf ("%d\n", f[n + 1][m + 1]);
		return 0;
	}
}

int main () {
	string str = "subsequence";
	freopen((str + ".in").c_str(), "r", stdin);
	freopen((str + ".out").c_str(), "w", stdout);
	Main::main();
	return 0;
}