题解：AT_abc446_g [ABC446G] 221 Subsequence

· · 题解

感谢这题把我送上等级分 1597，表现力 2010。/hec

dp 优化板题。

先列出一个朴素 O(n^2) 的 dp：f_{i,j} 表示到第 i 位，这个数已经重复 j 次。朴素转移是 O(1) 的，肯定过不了。

考虑整体转移。设 f_i 为以第 i 位之前为结尾，合法子序列的方案数。也就是对普通状态加前缀和。维护一个 l_i，使区间 [l_i, i] 中有 a_i 个 a_i。这部分可以用双指针解决，具体见代码，此处不展开。然后转移。

本题要求将子序列去重！！

打了好长时间的假算。/qd

这还不简单，直接计算 l_i 到 l_i 前第一个出现的 a_i 为止，中间的贡献。做完了。

好抽象啊，看代码吧。

https://atcoder.jp/contests/abc446/submissions/73507998