1400 : Composition

Description
Alice writes an English composition with a length of N characters. However, her teacher requires that M illegal pairs of characters cannot be adjacent, and if 'ab' cannot be adjacent, 'ba' cannot be adjacent either.
In order to meet the requirements, Alice needs to delete some characters.
Please work out the minimum number of characters that need to be deleted.
Input
The first line contains the length of the composition N.
The second line contains N characters, which make up the composition. Each character belongs to 'a'..'z'.
The third line contains the number of illegal pairs M.
Each of the next M lines contains two characters ch1
and ch2,which cannot be adjacent.
For 20% of the data: 1 ≤ N ≤ 10
For 50% of the data: 1 ≤ N ≤ 1000
For 100% of the data: 1 ≤ N ≤ 100000, M ≤ 200.
Output
One line with an integer indicating the minimum number of characters that need to be deleted.
Sample Hint
Delete 'a' and 'd'.
Sample Input
5
abcde
3
ac
ab
de
Sample Output
2

思路分析
动态规划。记录变量dp[i]为以i字符结尾的最小删除字符数。
过程中，要记录26个字母最后一次出现的位置（否则遍历前面所有字符将TLE）。
对每一个位置i，首先将dp[i]赋值为i，因为若想以i结尾，最简单的方式就是删除前面所有字符。想要以s[i]结尾，则上一个字符必须可以与s[i]相邻出现，那么挑出a-z中可以与s[i]相邻的字母char，char最后一次出现位置为p，则一种删除方式是在p位置以char结尾的删除方式，加上删除p位置和i位置之间的字母。
AC代码

#include <iostream>
#include <string>

using namespace std;

int main() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    int m;
    cin >> m;
    char c1, c2;
    //the index
    int opt[26];
    for (int i = 0; i < 26; i++)
        opt[i] = -1 ;
    int limit[26][26] = { false };
    for (int i = 0; i < m; i++) {
        cin >> c1;
        cin >> c2;
        limit[c1 - 'a'][c2 - 'a'] = true;
        limit[c2 - 'a'][c1 - 'a'] = true;
    }
    if (n <= 1)
        return 0;
    int dp[100000] = { 0 };
    opt[s[0] - 'a'] = 0;
    int min;
    int rst = n;
    
    for (int i = 1; i < n; i++) {
        min = i;
        for (int j = 0; j < 26; j++) {
            if (opt[j] >= 0 && !limit[s[i] - 'a'][s[opt[j]] - 'a']) {
                if (dp[opt[j]] + i - opt[j] - 1 < min)
                    min = dp[opt[j]] + i - opt[j] - 1;
            }
        }
        dp[i] = min;
        opt[s[i] - 'a'] = i;
        if (min + n - i - 1 < rst)
            rst = min + n - i - 1;
    }
    cout << rst;
    return 0;
}