题解 P2187 【小Z的笔记】

Siyuan · 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} 转移方程：

显然整个转移方程的复杂度为 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;
}