题解 P2187 【小Z的笔记】

Siyuan

2019-02-08 11:19:36

Solution

[$$\Large\texttt{My Blog}$$]() --- ## Description > 题目链接:[Luogu 2187](https://www.luogu.org/problemnew/show/P2187) 小 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 ```cpp #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; } ```