虽然感觉神仙但是又感觉不神仙。。。
对于删除,一定是删掉连续的一段的
如果可以预处理出某一段能不能被删掉,我就很开心了
设f[i][j][k][u]表示给出的字符串中,i到j和S集合第k个元素第u个字符是否匹配
转移懒得写了反正抄的
#include<cstdio> #include<iostream> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> using namespace std; int n,m,len[35]; char sc[160],S[35][25]; bool f[160][160][35][25],c[160][160]; int g[160]; int main() { freopen("a.in","r",stdin); freopen("a.out","w",stdout); scanf("%s",sc+1),n=strlen(sc+1); scanf("%d",&m); for(int i=1;i<=m;i++) scanf("%s",S[i]+1),len[i]=strlen(S[i]+1); for(int i=n;i>=1;i--) for(int j=i;j<=n;j++) { if(i==j) { for(int k=1;k<=m;k++) if(sc[i]==S[k][1])f[i][i][k][1]=true; } else { for(int k=1;k<=m;k++) for(int u=1;u<=len[k];u++) { if(f[i][j-1][k][u-1]&&sc[j]==S[k][u])f[i][j][k][u]=true; for(int p=i;p<=j;p++) if(f[i][p][k][u]&&c[p+1][j])f[i][j][k][u]=true; } } for(int k=1;k<=m;k++) if(f[i][j][k][len[k]])c[i][j]=true; } memset(g,63,sizeof(g));g[0]=0; for(int i=1;i<=n;i++) for(int j=0;j<i;j++) g[i]=min(g[i],g[j]+(i-j)*(!c[j+1][i])); printf("%d\n",g[n]); return 0; }