# 2021NC多校05-D(DP+二维前缀和)

2021NC多校05-D

题意:

给出两个字符串A和B,请你从A里选一个子序列a,B里选一个子序列b,使得ab长度相同同时a<b,有多少种选法。

\(length(A),length(B) \leq 5000\)

题解:

定义\(f[i][j]\)\(A\)\(i\)为止,\(B\)\(j\)为止的公共子序列方案数。

定义\(g[i][j]\)\(A\)\(i\)为止,\(B\)\(j\)为止,在选\(A[i],B[j]\)的前提下,公共子序列的方案数。

那么对每个\(i\)\(j\),有:

\(f[i][j]=f[i][j-1]+f[i-1][j]-f[i-1][j-1]\)

如果\(A[i]=B[j]\),有:

\(f[i][j]=f[i][j]+f[i-1][j-1]+1\)

\(g[i][j]=g[i-1][j-1]+1\)

定义\(q[i][j]\)为从\(A[i],B[j]\)开始往后,在\(A\)\(B\)内选长度相同的任意子序列的方案数。

定义\(p[i][j]\)为当\(A[i]<B[j]\)时,在选\(A[i],B[j]\)的前提下往后在\(A\)\(B\)内选长度相同的任意子序列的方案数。

定义\(z[i][j]\)为在\(i,j\)之后,\(p[i][j]\)的二维后缀和。

那么对于每个\(i\)\(j\),有:

\(q[i][j]=q[i+1][j]+q[i][j+1]-q[i+1][j+1]+q[i+1][j+1]+1\)

如果\(A[i]<B[j]\),有:

\(p[i][j]=q[i+1][j+1]+1\)

\(z[i][j]=p[i+1][j]+p[i][j+1]-p[i+1][j+1]+p[i][j]\)

可以把答案分为两类。

一类是从第一个字符开始就满足\(a[0]<b[0]\)的,这类答案的数量显然是\(z[1][1]\)

一类是存在一个\(k\)满足\(1 \leq i \leq k-1,a[i]=b[i]\),且\(a[k]<b[k]\)的。这类答案的数量可以这样算:

枚举\(A[i]\)\(B[j]\),在\(i\)\(j\)之前选公告子序列,之后选满足第一个选择的位置\(A[k]<B[k]\)的子序列,答案就是\(z[i][j] \times g[i][j]\)

这题还有几个坑:卡内存,数组最多开两个,且不能开long long,这里需要调整一下处理顺序,反复复用两个数组。

# 2021NC多校05-D(DP+二维前缀和)

上一篇:Symbol - 看似平凡的Symbol其实我们每天都在用


下一篇:mybatis-generator 整合lombok