bzoj2121

题意

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

限制条件

|L|<=150

|S[i]|<=20

|S|<=30

题解

设置dp[i][j][k][t]代表L的子串L[i,j],能否实现删除之后,可以匹配S中第k个串的前t个字符。

转移的时候

若匹配成功时,考虑第j位,若还在串中,且有L[j]==S[k][t],则可以由dp[i][j-1][k][t-1]转移过来

若此位不在,肯定是被其他S=消除了,则考虑枚举ij中间的d,若存在一个k’,若dp[d][j][k’][len[k’]]==true (len[k’]代表k’串的长度),说明存在某方法消掉区间d..j 于是dp[i][j][k][t]可以由dp[i][d-1][k][t]转移过来。

综合:转移依赖于dp[i][j-1][k][t-1]dp[d][j][k’][len[k’]]dp[i][d-1][k][t]

仔细观察,区间长度是关键,这些区间长度都比区间ij小,我们只需要从小到大枚举区间长度,即可成功转移,时间复杂度$(151\times 151\times 31\times 21) \times (151\times 31)$

这里转移过程时间复杂度太大了,也不利于转移,我们紧接着发现一个可以优化的地方,dp[d][j][k’][len[k’]]这里的枚举k’是可以优化的,它的本质是看看能否消掉区间d..j,我们用另外一个数组crm[i][j](如果能移除子串L[i,j],则crm[i][j]=true)来记录一下即可,于是时间复杂度$(151\times 151\times31\times21) \times31$

$4\times108$这样的时间复杂度已经可以了,

我们再来看如何转移到答案,其实只需要crm[][]即可,我们用mln[i]数组来代表前i项经过操作后能留下的最短的串的长度,

mln[i]如果保留最后一个字符则可以由mln[i-1]+1转移

否则可以由mln[d]转移,前提是crm[d+1][i]=true,区间[d+1,i]可以被消掉。

最终答案在mln[strlen[L]]中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include<bits/stdc++.h>
using namespace std;

char L[160],S[40][30];
int len[40];
bool crm[160][160];//crm[i][j] -> can remove L[i..j]
int mln[160];//mln[i] -> min len -> L[1..i]经过操作后能够变得最短的长度
bool dp[160][160][40][30];//dp[i][j][k][t] -> 代表L[i..j]能够删成串k的前t项

int main(){

int n;
scanf("%s%d",L+1,&n);
for(int i=1;i<=n;i++){
scanf("%s",S[i]+1);
len[i]=strlen(S[i]+1);
}

int lenL=strlen(L+1);

for(int i=1;i<=lenL;i++){
for(int k=1;k<=n;k++){
dp[i][i-1][k][0]=true;
}
}

for(int len_seg=1;len_seg<=lenL;len_seg++){
for(int i=1;i+len_seg-1<=lenL;i++){
int j=i+len_seg-1;
for(int k=1;k<=n;k++){
for(int t=1;t<=len[k];t++){
dp[i][j][k][t]=false;
if(L[j]==S[k][t])dp[i][j][k][t]=dp[i][j-1][k][t-1];
for(int d=i;d<=j;d++){
if(crm[d][j]&&dp[i][d-1][k][t])dp[i][j][k][t]=true;
}
}
if(dp[i][j][k][len[k]])crm[i][j]=true;
}
}
}

for(int i=1;i<=lenL;i++){
mln[i]=mln[i-1]+1;
for(int j=1;j<=i;j++){
if(crm[j][i])mln[i]=min(mln[i],mln[j-1]);
}
}

cout<<mln[lenL]<<endl;
}