题解 P2187 【小Z的笔记】

DDOSvoid · 2018-08-02 15:37:46 · 题解

思路：首先能判断这是个 dp，贪心的从前往后删显然是错的。

那么先有一个朴素的 dp 方程，f[i] 表前 i 个满足条件（包括第 i 个，最少删几个。那么转移只需要枚举一个 j，如果 i 和 j 可以相邻，则可以拿 f[j] 来更新 f[i]，即 f[i]=min(f[i],f[j]+i-j-1) 就是把 j + 1 ~ i - 1 都删掉。

至于判断是可以做到 O(1)，即只需要拿一个二维数组记录两个字母之间是否可以相邻。

上面的 dp 的复杂度是 O(n^2) 的，考虑优化。

发现转移的过程实际上是找一个最小的 f[j]-j，那么我们只需要记录每个字母的最小的 f[j]-j 即可，这样每次转移的复杂度是 O(26)，总的复杂度是 O(26n)，那么这题就做完了

#include<iostream>
#include<cstdio>
#include<cstring>
#define maxn 100010
#define maxm 410
using namespace std;

int n, m;
char s[maxn], c[3];
int ma[50][50];

int f[maxn];
int g[26];

int main(){
    scanf("%d%s", &n, s + 1);
    scanf("%d", &m);
    for(int i = 1; i <= m; ++i){
        scanf("%s", c+ 1);
        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);
        }
        g[s[i] - 'a'] = min(g[s[i] - 'a'], f[i] - i);
    }
    cout << f[n];
    return 0;
}