【BZOJ 2121】（字符串DP，区间DP）

今天药忘吃喽~ 2021-10-01 00:08 409阅读 0赞

> ## 2121: 字符串游戏 ##
> 
> ## 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  
> 
> 
> ## HINT ##
> 
> ## Source ##

【分析】

感觉我的字符串DP弱弱的。

数据很小。。。

所以，。。

令dp\[i\]\[j\]\[k\]\[l\]表示母串中左端点为i，右端点为j，能否删到只剩下第k个字符串的前l位，ok\[i\]\[j\]表示母串i~j能否删完，显然有ok\[i\]\[j\]=dp\[i\]\[j\]\[k\]\[len\[k\]\]的并。

两种情况转移一下即可。

大神的压后面的做法好美丽！

[http://blog.csdn.net/lych\_cys/article/details/51164134][http_blog.csdn.net_lych_cys_article_details_51164134]

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<iostream>
     2 #include<cstdio>
     3 #include<cstring>
     4 using namespace std;
     5 #define Maxl 160
     6  
     7 int n,m,len[40],bin[30];
     8 int p[Maxl][30],dp[Maxl][30];
     9 int f[Maxl];
    10 char s[Maxl],a[30][40];
    11 bool ok[Maxl][160];
    12 
    13 int mymin(int x,int y) {
         return x<y?x:y;}
    14 
    15 int main()
    16 {
    17     scanf("%s",s+1); m=strlen(s+1);
    18     scanf("%d",&n);
    19     for(int i=1;i<=n;i++)
    20     {
    21         scanf("%s",a[i]+1); len[i]=strlen(a[i]+1);
    22     }
    23     bin[0]=1;
    24     for(int i=1;i<=22;i++) bin[i]=bin[i-1]<<1;
    25     for(int i=1;i<=m;i++)
    26      for(int j=1;j<=n;j++)
    27       for(int k=1;k<=len[j];k++) if(s[i]==a[j][k]) p[i][j]|=bin[k];
    28     
    29     for (int i=m;i>=1;i--)
    30     {
    31         for(int j=1;j<=n;j++) dp[i-1][j]=1;
    32         for(int j=i;j<=m;j++)//i~j
    33         {
    34             for(int k=1;k<=n;k++)
    35             {
    36                 dp[j][k]=(dp[j-1][k]<<1)&p[j][k];
    37                 for(int l=i;l<j;l++) if(ok[l+1][j]) dp[j][k]|=dp[l][k];
    38                 if(dp[j][k]&bin[len[k]]) ok[i][j]=1;
    39             }
    40         }
    41     }
    42     for(int i=1;i<=m;i++)
    43     {
    44         f[i]=f[i-1]+1;
    45         for(int j=1;j<=i;j++) if(ok[j][i])
    46            f[i]=mymin(f[i],f[j-1]);
    47     }
    48     printf("%d\n",f[m]);
    49     return 0;
    50 }

2017-03-20 10:26:02

转载于:https://www.cnblogs.com/Konjakmoyu/p/6586335.html

[http_blog.csdn.net_lych_cys_article_details_51164134]: http://blog.csdn.net/lych_cys/article/details/51164134
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20210724/5a6d183387c644d7b85058ad12c2d365.png