主页
搜索
最近更新
数据统计
申请密钥
批量保存
开发版网站（新前端）
系统公告
1
/
1
请查看完所有公告
题解：CF682D Alyona and Strings
最后更新于 2025-08-28 09:02:54
作者
2huk
分类
题解
题解
CF682D
复制 Markdown
查看原文
转到新前端
删除文章
更新内容
经典题。 考虑 DP。设 $f(i, j, k, 0/1)$ 表示只考虑 $s_{1\dots i},t_{1\dots j}$，总共选了 $k$ 个**非空**子串，且 $s_i, t_j$ 是否**匹配**。 这里比较重要的是第四维。**匹配**的意思是指，$s_i, t_j$ 最终都被选择，且都被选择在了同一个（也就是第 $k$ 个）子串里。同理，不匹配就是指 $s_i, t_j$ 中有至少一个没有被选择。 考虑转移： $$ f(i, j, k, 0) = \max\{f(i-1,j-1,k,0/1), f(i-1,j,k,0/1), f(i,j-1,0/1)\} \\ f(i,j,k,1) = \begin{cases}\max\{f(i-1,j-1,k,1),f(i-1,j-1,k-1,0)\} + 1 & s_i = t_j \\ 0 & s_i \ne t_j\end{cases} $$ $f(i, j, k, 0)$ 不难理解。$f(i, j, k, 1)$ 中的 $\max\{f(i-1,j-1,k,1),f(i-1,j-1,k-1,0)\} + 1$ 是指，要么 $i, j$ 和上一个子串接起来，要么重开一个，但是最终都要 $+1$ 表示被选择的数多了一个。 原题允许子串为空，但我们的状态里规定不为空，所以答案不是 $f(n, m, k, 0/1)$ 而是 $\max_{i \le k} f(n, m, i, 0/1)$。
正在渲染内容...
点赞
0
收藏
0
