题解：P2187 小Z的笔记

· · 题解

题目传送门

Part 1 题意简述。

有一个长度为 n 的序列，规定有 m 个字母对不能相邻，并且是与字母顺序无关的。求最少要去掉多少个字母，使得整个序列合法。

Part 2 解法。

本题求最少要擦除的字母数，求最值可选用 DP 大法。

来推这题的方程：f_i 表示前 i 个满足条件（包括第 i 个，最少删几个。那么转移只需要枚举一个 j，如果 i 和 j 可以相邻，则可以拿 f_i 来更新 f_j。

然后，我们就得出了式 f_i=\min(f_i,f_j+i-j-1)。 但是时间复杂度爆了，优化一下（把带有 i 的项提出）。然后，我们就得到了这个 f_i=\min{f_j-j}+i-1。

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
int n, m,ma[50][50],f[maxn],g[26];
char s[maxn], c[3];
int main() {
    cin>>n;
    cin>>s+1;//一定要注意加一，不然会WA
    cin>>m;
    for(int i = 1; i <= m; ++i) {
        cin>>c+1;//一定要注意加一，不然会WA
        c[1] -= 'a';//处理字符
        c[2] -= 'a';
        ma[c[1]][c[2]] = ma[c[2]][c[1]] = 1;
    }
    memset(f, 10, sizeof f);
    f[1] = 0;
    g[s[1] - 'a'] = 0 - 1;
    for(int i = 2; i <= n; ++i) {
        for(int j = 0; j < 26; ++j) {
            if(ma[s[i] - 'a'][j]) continue;
            f[i] = min(f[i], g[j] + i - 1);//dp式子 
        }
        g[s[i] - 'a'] = min(g[s[i] - 'a'], f[i] - i);//记得修改g数组 
    }
    cout << f[n];//经典dp题输出 
    return 0;
}

感谢大佬帮助：@ Para @DDOSvoid @ Siyuan。

如有问题，欢迎提出。