小 W W 理 筆記
【問題 描 述】
小 W 由于購物浪費了太多時間，導緻他外語課都沒有好好聽。為什麼是外語課？不是英
語課？因為小 W 肯定會好好聽英語課。由于沒有好好聽課， 小 W 的筆記全都記的雜亂無章，
出現了好多錯誤的地方。 小 W 的筆記是如此的糟糕，以至于他隻記了一句例句，而且自己
還不知道是什麼意思……然後在老師講文法的時候， 小 W 又零星的記了幾個字母對，老師
說：這幾個字母對是絕對不能相鄰的，而且相鄰是不關心字母的順序的，比如老師說，‘ab’
不能相鄰，那麼相同的，‘ba’也不能相鄰。
現在小 W 到家了，打開了上課的筆記，然後他發現筆記有很多自相沖突的地方：為什
麼下面的不能相鄰的字母對會出現在上面的例句裡面呢？糾結再三， 小 W 覺得下面的東西
相對比較簡單，是以記錯的機率比較小……他決定在上面的例句裡面擦掉幾個字母，使得句
子變得合法。
但是小 W 還要把禮物送給小 M，來不及整理筆記了，就把這個艱巨的任務留給了大家，
請問大家， 小 W 最少要擦掉幾個字母，才能使得上面的例句合法？
【輸入格式】
第一行：一個整數 N。
第二行：一個長度為 N 的字元串，隻包含小寫字母，代表小 W 記下的例句。
第三行：一個整數 M，代表不能相鄰的字母對的個數。
接下來 M 行：每行兩個小寫字母，代表不能相鄰的字母對，因為小 W 太不認真了，是以可
能有重複。
【輸出格式】
一行一個整數：最少要擦除的字母數。
【輸入輸出樣例】
note.in note.out
4 1
jsoi
2
oi
mo
【 資料規模 】
對于 10%的資料，M=0
對于另外 30%的資料，N≤1000
對于 100%的資料，N≤100000，M≤400
分析：
可以看出題目的無後效性，是以采用dp的做法。
我們定義狀态f[i]表示前i個字元所需擦去的最小個數，是以有f[i]=min(f[j]+(i-j)),且j是可以與i相鄰的字元。
效率O(n^2)，顯然不夠。
我們再來看一看轉移方程，由于可以與i相鄰的j總共隻可能是26種字元，是以我們可以維護M(j)表示最後一位保留j字元的最小擦去數，但是我們還要維護對應的j的位置，否則怎麼計算(i-j)呢？仍然有兩個因素限制結果，如果采取枚舉一個計算另一個的做法，效率就沒有降低。
如果我們不計算最小擦去數，而反過來計算最大保留數呢？
那麼f[i]=max(f[j]+1),維護一個M(j),顯然就可以解決問題，将複雜度降為O(n)
參考程式：
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=110000;
int f[maxn],g[maxn];
int last[30],forbid[30][30];
char b[maxn];
int n,m;
int main(){
freopen("note.in","r",stdin);
freopen("note.out","w",stdout);
scanf("%d",&n);
scanf("%s",b+1);
for (int i=1;i<=n;i++)
f[i]=b[i]-'a';
scanf("%d",&m);
while (m--){
scanf("%s",b);
forbid[b[0]-'a'][b[1]-'a']=forbid[b[1]-'a'][b[0]-'a']=1;
}
int ans=0;
for (int i=1;i<=n;i++){
g[i]=1;
for (int j=0;j<26;j++)
if (!forbid[j][f[i]])
g[i]=max(g[i],last[j]+1);
last[f[i]]=max(last[f[i]],g[i]);
ans=max(ans,g[i]);
}
printf("%d",n-ans);
return 0;
}