自动搬运

查看原文

来自洛谷，原作者为

	Siyuan Dream OIer.

搬运于2025-08-24 21:34:55，当前版本为作者最后更新于2019-02-08 11:19:36，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

$$\Large\texttt{My Blog}$$

---

Description

题目链接：Luogu 2187

小 Z 的有一个长度为 $n$ 的笔记，他规定有 $m$ 个字母对不能相邻，并且是与字母顺序无关的。现在给出这个笔记，请求出最少需要擦掉多少个字母，使得整个笔记合法。

数据范围：$1\le n\le 10^5$，$1\le m\le 400$

---

Solution

我们可以很容易地写出朴素的 $\text{DP}$ 转移方程：

$$f_i=\min\{f_j+i-j-1\}\quad(0\le j<i,\text{第}\ i\ \text{个字母和第}\ j\ \text{个字母可以相邻}) $$

显然整个转移方程的复杂度为 $O(n^2)$，我们考虑如何优化。首先我们把带有 $i$ 的项提出，得到 $f_i=\min\{f_j-j\}+i-1$，那么这个方程的实质就是求出最小的 $f_j-j$。我们对于每个字母 $i$ 维护一个 $f_i-i$ 的最小值 $g_i$，每次枚举上一个字母 $k$，用 $g_k+i-1$ 来更新 $f_i$ 即可。

时间复杂度：$O(26\cdot n)$

---

Code

#include <cstdio>
#include <algorithm>

const int N=1e5+5;
int n,f[N],g[30];
char s[N];
bool e[30][30];

char getc() {
	char c=getchar();
	while(c<'a'||c>'z') c=getchar();
	return c;
}
int main() {
	scanf("%d%s",&n,s+1);
	int m;
	for(scanf("%d",&m);m--;) {
		int u=getc()-'a',v=getc()-'a';
		e[u][v]=e[v][u]=1;
	}
	for(int i=1;i<=n;++i) {
		f[i]=1<<30;
		for(int j=0;j<26;++j) if(!e[s[i]-'a'][j]) f[i]=std::min(f[i],g[j]+i-1);
		g[s[i]-'a']=std::min(g[s[i]-'a'],f[i]-i);
	}
	printf("%d\n",f[n]);
	return 0;
}