做不出来杂题,到处找题做
看到$loj$上新出了一道题,觉得很神仙不错,
还记得Censoring吗(一个AC自动机的题)
这个题求最优解,数据范围$150$
题解
数据范围非常小,首先贪心肯定不行,考虑AC自动机上$dp$?
好吧其实是区间$dp$
一个直接的想法是维护$f[l][r]=0/1$表示是否可以清空$l$,$r$这一段子段
然而转移起来很难转移,考虑再定义一个数组$g[l][r][i][w]=0/1$表示是否可以清成第$i$个模式串的前$w$位
考虑$g$转移,
1.直接匹配$g[l][r][i][w]|=g[l][r-1][i][w-1]$其中主串$str[r]==c[i][w]$表示若$l,r-1$可以清成第$i$个模式串前$w-1$位那么若当前两个可以匹配上必然$l,r$可以清成第$i$个模式串前$w$位
2.由几部分拼凑$g[l][r][i][w]|=g[l][q-1][i][w]\&f[q][r]$表示$q-r$被清空那么$g$显然可以转移
那么根据$f$定义$f[l][r]|=g[l][r][i][len[i]]$
举个例子$momooo$ 模式串$moo$
先$g[3][5][1][3]=1$,得$f[3][5]=1$得$g[1][5][1][2]=1$(由$f[3][5]$)转移 再进行一步匹配$f[3][6][1][3]=1$得$f[1][6]=1$可以全部清空
那么$ans$根据类似最长上升子序列求
$ans[i]=min(ans[i-1]+1,ans[l-1](f[l][i]==1))$两层循环枚举
考虑炸内存?
状压,怎么状压,压掉一维,这里不再解释,因为数据点足够水,这已经足以通过测试点
代码
using namespace std;
#define A 152
#define ll long long
ll len[A],ans[A];
bool f[A][A],g[A][A][52][52];
ll n,cnt;
char c[A][A],str[A];
int main(){
scanf("%s",str+1);
n=strlen(str+1);
scanf("%lld",&cnt);
for(ll i=1;i<=cnt;i++){
scanf("%s",c[i]+1);
len[i]=strlen(c[i]+1);
}
for(ll i=1;i<=n;i++){
f[i][i-1]=1;
for(ll j=1;j<=cnt;j++){
g[i][i-1][j][0]=1;
}
}
for(ll k=1;k<=n;k++){//枚举当前长度
for(ll l=1;l<=n-k+1;l++){
ll r=l+k-1;
for(ll w=1;w<=cnt;w++){
for(ll now=1;now<=len[w];now++){
if(c[w][now]==str[r])
g[l][r][w][now]|=g[l][r-1][w][now-1];
}
for(ll now=1;now<=len[w];now++){
for(ll i=l;i<=r;i++){
g[l][r][w][now]|=g[l][i-1][w][now]&f[i][r];
}
}
}
for(ll w=1;w<=cnt;w++)
f[l][r]|=g[l][r][w][len[w]];
}
}
for(ll i=1;i<=n;i++){
ans[i]=ans[i-1]+1;
for(ll j=1;j<=i;j++){
if(f[j][i]){
ans[i]=min(ans[i],ans[j-1]);
}
}
}
printf("%lld\n",ans[n]);
}