CF154A Hometask
给定一个字符串，还有 个只有两个字符的串，问需要在原串中删除多少个字符才能保证原串中不含这
个串及其反向串。
没救了，就我一个用 DP 做……
先考虑设 表示使得前
个字符满足条件，最多能保留多少个字符。我们可以分两种情况讨论：
- 第
个字符删去，此时
。
- 保留第
最优的时候的最后一个字符是什么，这就没法推导了。
为了记录保留的最后一个字符，我们可以给 加一维。设
表示前
个字符，最后一个保留的字符是
，在满足条件的情况下最多能保留的字符数。再分两种情况讨论：
- 第
。
- 保留第
，
是原串），对于任何可以与字符
拼接在一起的字母
，
。
另：我们要将 初始化为
，因为某些情况是不可能的。还有，
。
此时我们的程序会被 Hack：
abcdefg
6
ab
ac
ad
ae
af
ag
按照上面的方法会输出 （最多能保留
个字符），答案是
。这是为什么？因为我们还没有考虑前
个字符全部删去的情况。我们设
表示前
个字符全部删去的情况，数值为
，
任选；或者当
时，
，因为肯定能保留第
个字符。
因为上面已经很详细，代码就不写注释了。
#include<cstdio>
#include<cstring>
using namespace std;
int n,k,f[100010][27],ans; char str[100010],tmp[5];
bool use[10010];
inline int maxx(int a,int b){
return a>b?a:b;
}
int main(){
scanf("%s",(str+1));
n=strlen(str+1);
scanf("%d",&k);
for(int i=1;i<=k;i++){
scanf("%s",tmp);
use[(tmp[0]-'a')*26+(tmp[1]-'a')]=true;
use[(tmp[1]-'a')*26+(tmp[0]-'a')]=true;
}
memset(f,128,sizeof f);
f[1][str[1]-'a']=1; f[1][26]=0;
for(int i=2;i<=n;i++){
for(int j=0;j<=25;j++){
if(str[i]-'a'==j){
for(int k1=0;k1<=25;k1++){
if(!use[j*26+k1]) f[i][j]=maxx(f[i][j],f[i-1][k1]+1);
}
f[i][j]=maxx(f[i][j],f[i-1][26]+1);
}
f[i][j]=maxx(f[i][j],f[i-1][j]);
}
f[i][26]=0;
}
for(int j=0;j<=25;j++) ans=maxx(ans,f[n][j]);
printf("%d\n",n-ans);
return 0;
}
