bzoj2121 字符串游戏 题解【区间DP】

作者: wjyyy 分类: DP,区间DP,解题报告 发布时间: 2019-07-06 08:19

点击量:113

区间 DP 的新经典套路。

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

HINT

对于 $100\%$ 数据,满足 $|L|<151,|S|<31$,$S$ 中的每个元素 $|p|<21$。

题解

区间 DP 一般会解决在序列上的问题。

我们使用较多的区间 DP 主要是合并一些不交区间的信息来统计答案,不过还有一种经典的区间 DP 可以同时处理不交区间和区间互相包含的问题。

本题的棘手之处在于删掉一段子串之后可以迭代继续删除,而此时这种区间是互相包含的,而且不容易方便地判断迭代的情况。

对于这种 DP 题目,我们需要同时进行两个 DP,以判断当前区间内是否包含一个子区间可以被删除;而这个信息需要通过记录该区间是否能匹配集合 $S$ 中的某个字符串来计算。

因此我们维护两个布尔数组。

$f[l][r][i][j]$ 表示串 $L$ 的区间 $[l,r]$ 是否能被删成集合 $S$ 中第 $i$ 个字符串的前 $j$ 个字符,也就是与 $S_i$ 的前 $j$ 个字符匹配。

$g[l][r]$ 表示串 $L$ 的区间 $[l,r]$ 是否能被删完。

$g[l][r]$ 很好计算,只需要存在 $i$ 使得 $f[l][r][i][len(i)]$ 为真就可以了。

而当 $L[r]=S_i[j]$ 时,有 $f[l][r][i][j]=f[l][r-1][i][j-1]$,并且如果 $r-1$ 前面一段可以被删除,就可以向前转移了。这种情况下存在 $k\in[l,r-1]$ 满足 $g[k][r-1]$ 为真,则可以转移 $f[l][r][i][j]=f[l][k][i][j-1]$。

上面两种转移来源是用或运算来汇总的。

发现此时 $f,g$ 好像互相引用了,事实上 $f$ 的转移方程是引用了比当前正在 DP 的 $[l,r]$ 更短的 $[k,r-1]$,因此 DP 可以从短到长的区间进行。

时间复杂度 $O(m^3\sum|p|)$,常数很小,上界很松。

Code:

#include<cstdio>
#include<cstdlib>
#include<cstring>
char s[155];
char t[32][22];
int l[32],dp[155];
bool f[155][155][32][22];
bool g[155][155];
int main()
{
    scanf("%s",s+1);
    int n,m=strlen(s+1);
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
    {
        scanf("%s",t[i]+1); 
        l[i]=strlen(t[i]+1);
    }
    for(int i=1;i<=m;++i)
    {
        for(int j=1;j<=n;++j)
            f[i][i-1][j][0]=1;
        for(int j=1;j<=i;++j)
            for(int k=1;k<=n;++k)
                for(int r=1;r<=l[k]&&r<=i-j+1;++r)
                    if(s[i]==t[k][r])
                    {
                        f[j][i][k][r]|=f[j][i-1][k][r-1];
                        for(int q=j;q<i;++q)
                            if(g[q][i-1])
                                f[j][i][k][r]|=f[j][q-1][k][r-1];
                        if(r==l[k])
                            g[j][i]|=f[j][i][k][r];
                    }
    }
    for(int i=1;i<=m;++i)
    {
        dp[i]=dp[i-1]+1;
        for(int j=1;j<=i;++j)
            if(g[j][i])
                dp[i]=dp[i]<dp[j-1]?dp[i]:dp[j-1];
    }
    printf("%d\n",dp[m]);
    return 0;
}

说点什么

avatar
  Subscribe  
提醒
/* */