• 周二. 8月 16th, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

快乐的一天从AC开始 | 20210726 | P5484

admin

11月 28, 2021

题目链接

因为台风今天又能提早下班

点了夜宵结果没有骑手接单,不过这种天气也正常

好饿,等会儿再去嫖室友的泡面ali

心路历程

这不是编辑距离改改就完事了?

光速码完,啊题目怎么是算方案数啊?

思路

首先可以将(T)变为与(T)匹配的串,然后题目转化为(S)有多少个子序列与(T)相等。

然后就是DP了,记(dp_{i,j})表示(s_{1 dots i})(t_1 dots j)的答案。如果(s_i = t_j),则之前匹配上了的子序列都能加上(s_i)且保持匹配,否则只能继续用之前匹配的子序列。写成转移方程就是

[dp_{i, j} =
left{
egin{array}{}
dp_{i – 1, j} + dp_{i – 1, j – 1}\
dp_{i – 1, j}
end{array}
ight.
]

现在应该就足够AC了,不过注意到每次都只于前一轮有关,所以可以搞个滚动数组优化空间。

然后就是边界情况了,如果(S)(T)有相同字符串组成,那么答案就是(C_{n}^{m}),这个在本题的条件下会爆精度,所以还得写个高精度。

发表回复

您的电子邮箱地址不会被公开。