bzoj2121 字符串游戏 题解【区间DP】
点击量:315
区间 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;
}
买快递单号的网站提供多家常用快递,选择88单号网www.88danhaowang.com