自动搬运

查看原文

来自洛谷，原作者为

	CommandSR I love Segment Tree | FR'F R2U'R'U'RUR'F' RU'R'U'F'

搬运于2025-08-24 22:57:33，当前版本为作者最后更新于2025-08-19 07:15:23，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意

link

Subtask 1

写一个爆搜，一个颜色可以跟上一个相同，也可以是接在上一个颜色后面新开一个颜色，最后递归出口要判每个颜色是或否全部出现。

Subtask 2

显然有一个 $O(n^2)$ 的 dp，设 $f_{i,j}$ 表示 $b$ 序列中前 $i$ 个数用 $j$ 种颜色填的最小修改次数。状态转移：

f[i][j] = min(f[i-1][j], f[i-1][j-1]) + (b[i] != c[j]);

Subtask 3

上面那个 dp 看起来没有前途，所以尝试以颜色划分阶段。

首先对相同颜色的段“缩点”，最后目标状态的 $b$ 和 $a$ 是相同的，为了方便处理把 $a$ 映射成一个递增的序列。

然后 $f_i$ 可以从 $f_j + i-j+1$ 转移，其中 $j<i$，$c_j\le c_i$，$c_i-c_j\le i-j$，第三个条件相当于要留足够的位置填所有颜色。

然后问题转化为三维偏序问题，复杂度 $O(n\log^2 n)$。

Subtask 4

考虑在上面 dp 的基础上优化，首先我们按照颜色转移，可以确定 $c_j\le c_i$，然后发现 $i<j$ 时一定不满足第三个式子，把第三个式子化为 $c_i-i\le c_j-j$。最后以 $c_i$ 为第一关键字，$i$ 为第二关键字为顺序转移，最后用树状数组优化即可。复杂度 $O(n\log n)$。

Code

// Problem: P10395
#include <bits/stdc++.h>
#define db double
#define ll long long
#define pc putchar
#define gc getchar
#define sz(x) ((int)x.size())
#define F(i, a, b) for (int i = (a); i <= (b); ++i)
#define D(i, a, b) for (int i = (a); i >= (b); --i)
#define TM cout<<fabs(&Med-&Mbe)/1048576.0<<"MB "<<1.0*clock()/CLOCKS_PER_SEC*1000<<"ms\n"
bool Mbe;
using namespace std;
namespace IO {
#define typ ll
	inline typ rd() {
		typ x = 0; bool f = 1; char ch = gc();
		while (ch < '0' || ch > '9') { if (ch == '-') f = 0; ch = gc(); }
		while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = gc();
		return (f ? x : (-x));
	}
	inline void wr(typ x) {
		if (x < 0) pc('-'), x = -x;
		if (x > 9) wr(x / 10); pc(x % 10 + '0');
	}
}
using namespace IO;
// ----------------- Main Code -----------------
const int N = 2e6 + 5;
int n, m, a[N], c[N], id[N], k;
vector<int> G[N];
void upd(int p, int x) { ++p; for (int i = p; i <= m + 1; i += (i & -i)) c[i] = min(c[i], x); }
int qry(int p) { ++p; int res = 1e9; for (int i = p; i; i -= (i & -i)) res = min(res, c[i]); return res; }
int main() {
	n = rd(), m = rd();
	F(i, 1, n) {
		a[i] = rd();
		if (!id[a[i]]) id[a[i]] = ++k;
		else if (a[i] != a[i-1]) { wr(-1), pc('\n'); return 0; }
	}
	if (m < k) { wr(-1), pc('\n'); return 0; }
	F(i, 1, m) {
		int x = rd();
		G[id[x]].push_back(i);
	}
	memset(c, 0x3f, sizeof c);
	int ans = m;
	upd(0, 0);
	F(i, 1, k) {
		for (int v : G[i]) if (v >= i && m-v >= k-i) {
			int p = v - i; // 缩点后的编号
			int f_v = qry(p) + v - 1; // 树状数组中存的值是 f_i - i
			ans = min(ans, f_v + m - v);
			upd(p, f_v - v);
		}
	}
	wr(ans), pc('\n');
	return 0;
}