首页 > 小V和字符串
开通博客写题解
头像 Lskkkno1
发表于 2020-05-15 22:25:07
小V和字符串 题目描述 直接点开题目看描述吧。 正解 数位 dp。 设 表示考虑前 位，两串 的差值为 的方案数（后面两个 表示两个串分别是否顶上界）。 再设一个辅助数组 表示考虑前 位，两串 的差值为 ，的所有方案下，需要移动的步数（后面两个 与上面定义相同）。 发现如果当前两 展开全文
去ta的博客 赞 (6) 回复(1) 收起
头像 __CYJian__
发表于 2020-05-15 22:25:20
简单题。 考虑到有个性质： 若我们已经知道串 、 长啥样，就可以用这样的方式计算最小交换次数： ，考虑令 等于 的长度为 的前缀中 的出现次数 减去 的长度为 的前缀中 的出现次数，则跨过这个位置的交换一定至少有 步。 将所有位置的最小交换次数加起来，则可得到将 变成 的最小交 展开全文
去ta的博客 赞 (2) 回复(1) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”