简单DP 说是简单 还是推了好一会 推出来觉得好简单
保留当前i的最小值 dp[i] = min(dp[i],dp[j]+i-j-1) j<i
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
using namespace std;
#define INF 0xfffffff
char s[];
int w[][],dp[];
int main()
{
int i,j,k,n;
char a,b;
while(cin>>s)
{
memset(dp,,sizeof(dp));
memset(w,,sizeof(w));
cin>>n;
k = strlen(s);
for(i = ; i <= n ; i++)
{
cin>>a>>b;
w[a][b] = ;
w[b][a] = ;
}
dp[] = ;
for(i = ; i < k ; i++)
{
dp[i] = i;
for(j = i- ; j >= ; j--)
if(!w[s[i]][s[j]])
dp[i] = min(dp[i],dp[j]+i-j-);
}
int ans = INF;
for(i = ; i < k ; i++)
ans = min(ans,dp[i]+k-i-);
cout<<ans<<endl;
}
return ;
}