[洛谷]P2187 小Z的笔记

题目背景

小Z由于写情书浪费了太多时间，导致他外语课都没有好好听。为什么是外语课而不是英语课？因为小Z也不知道这门课学的是什么语言。

题目描述

由于没有好好听课，小Z的笔记全都记的杂乱无章，出现了好多错误的地方。小Z的笔记是如此的糟糕，以至于他只记了一句例句，而且自己还不知道是什么意思……然后在老师讲语法的时候，小Z又零星的记了几个字母对，老师说，这几个字母对是绝对不能相邻的，而且相邻是不关心字母的顺序的，比如老师说，“ab”不能相邻，那么相同的，“ba”也不能相邻。

现在小Z到家了，打开了上课的笔记，然后他发现笔记有很多自相矛盾的地方：为什么下面的不能相邻的字母对会出现在上面的例句里面呢？纠结再三，小Z觉得下面的东西相对比较简单，所以记错的概率比较小……他决定在上面的例句里面擦掉几个字母，使得句子变得合法。

但是小Z还有其他作业要做呢，来不及整理笔记了，就把这个艰巨的任务留给了大家，请问大家，小Z最少要擦掉几个字母，才能使得上面的例句合法？

输入输出格式

输入格式

第一行：一个整数N。

第二行：一个长度为N的字符串，只包含小写字母，代表小Z记下的例句。

第三行：一个整数M，代表不能相邻的字母对的个数。

接下来M行：每行两个小写字母，代表不能相邻的字母对，因为小Z太不认真了，所以可能有重复。

输出格式

一行，一个整数，最少要擦除的字母数。

输入输出样例

输入样例1

4
noip
2
ip
mo

输出样例1

说明

【数据规模】

对于10%的数据，M=0；

对于另外30%的数据，N<=1000；

对于100%的数据，N<=100000，M<=400。

代码

#include <bits/stdc++.h>
using namespace std;

const int maxn=1e5+10;
char s[maxn];
int n,m;
char x,y;
int f[maxn];
int can[100][100];
int ans;
int pt[100];

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>s[i],s[i]=s[i]-'a'+1;
    cin>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>x>>y;
        can[x-'a'+1][y-'a'+1]=1;
        can[y-'a'+1][x-'a'+1]=1;
    }
    memset(f,0x3f,sizeof(f));
    for(int i=1;i<=n;i++)
    {
        f[i]=1;
        for(int j=1;j<=26;j++)
            if(!can[j][s[i]])
                f[i]=max(f[i],pt[j]+1);
        pt[s[i]]=max(pt[s[i]],f[i]);
        ans=max(ans,f[i]);
    }
    cout<<n-ans<<endl;
}

[洛谷]小Z的笔记