bzoj2121 字符串游戏

bzoj2121 字符串游戏

​​ Description

BX正在进行一个字符串游戏，他手上有一个字符串L，以及其他一些字符串的集合S，然后他可以进行以下操作：对 于一个在集合S中的字符串p,如果p在L中出现，BX就可以选择是否将其删除，如果删除，则将删除后L分裂成的左右 两部分合并。举个例子，L=’abcdefg’ , S={‘de’}，如果BX选择将’de’从L中删去，则删后的L=’abcfg’。现在BX可 以进行任意多次操作（删的次数，顺序都随意），他想知道最后L串的最短长度是多少。 Input

输入的第一行包含一个字符串，表示L。 第二行包含一个数字n，表示集合S中元素个数。 以下n行，每行一个字符串，表示S中的一个元素。 输入字符串都只包含小写字母。 Output

输出一个整数，表示L的最短长度。

Sample Input

aaabccd 3 ac abc aaa Sample Output

2 【样例说明】 aaabccd aacd ad 对于100%数据,满足|L|<151,|S|<31,S中的每个元素|p|<21 设f[i][j][k][z]表示i~j区间能否凑出第k个子串的前z个 可以在i~j里面删除 并且可以把整个i~j区间完全删除 c[i][j]表示 i~j这个区间是否可以完全被删除 最后当求完所有的c和f之后我可以设dp[i]表示前i个我可以删到最短的是多少 那么n^2转移即可 关于f与c的转移我因为要用到后面的 所以我i=m~1这样转移 于是有方程 f[i][j][k][z]=f[i][j-1][k][z-1]&s[j]==sub[k][z] f[i][j][k][z]|=f[i][d][k][z]&&c[t+1][j]。

#include#include#includeusing namespace std;bool f[160][160][32][22],c[160][160];int ans[160],n,subl[32];char s[160],sub[32][22];int main(){ freopen("bzoj2121.in","r",stdin); scanf("%s",s+1);scanf("%d",&n);int l=strlen(s+1); for (int i=1;i<=n;++i) scanf("%s",sub[i]+1),subl[i]=strlen(sub[i]+1); for (int i=l;i;--i){ for (int j=i;j<=l;++j){ for (int k=1;k<=n;++k){ f[i][i-1][k][0]=1; for (int z=1;z<=subl[k];++z){ f[i][j][k][z]=(s[j]==sub[k][z]&&f[i][j-1][k][z-1]); for (int t=i;t

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。