0%

CF1336C

CF1336C

题意:给一个初始串$s$和目标串$t$,每次可以取出(并删除)$s$的第一个字符加入另一个串$A$的开头或末尾(初始为空),求$t$是$A$的前缀的方案数(任意一步操作不同即不同,$s$不必删完)

$|t|\le |s|\le 3000$

区间dp。令$f(l,r)$表示用$s$的前$r-l+1$个字符拼出$t_{l…r}$的方案数。(对于$i>|t|,t_i$可为任意字符)

边界:$t_i=s_1,f(i,i)=2$

转移:枚举长度$len$,和左端点$l$,则$r=l+len-1$。

  • 当$s_{len}=t_l,f(l,r)$可由$f(l+1,r)$转移而来
  • 当$s_{len}=t_r,f(l,r)$可由$f(l,r-1)$转移而来

最后的答案就是$\sum _{i=|t|}^{|s|} f(1,i)$

注意取模。时间复杂度$\mathcal O(n^2)$.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<bits/stdc++.h>
char s[3011],t[3011];
int f[3011][3011],yg=998244353;//yg txdy!!!
int main()
{
scanf("%s%s",s+1,t+1);
int n=strlen(s+1),m=strlen(t+1),res=0,i,j;
for(i=1;i<=n;++i)f[i][i]=(i>m||s[1]==t[i])*2;
for(int len=2;len<=n;++len)
for(i=1;i+len-1<=n;++i)
{
j=i+len-1;
if(i>m||s[len]==t[i])(f[i][j]+=f[i+1][j])%=yg;
if(j>m||s[len]==t[j])(f[i][j]+=f[i][j-1])%=yg;
}
for(i=m;i<=n;++i)(res+=f[1][i])%=yg;
printf("%d",res);
return 0;
}

还有一份更短的代码,现在是size排序rk2:link