1 条题解
-
0
题目分析
30 pts
对于30%的数据,有 。
如何统计一个给定串不同的子序列个数?
DP
- 表示字符 上一次出现的位置
- 表示以第 位结尾的新出现的不同子序列个数
考虑加入一个新的 ,那么所有以第 位()结尾的新出现的子序列,都可以加上一个 ,得到一个新的子序列。
如何证明 接上 不会形成新的子序列?
反证法
- 如果以 之前的某个位置为结尾的子序列接上第 位,会产生一个新的子序列,那么之前的子序列直接加上 也可以产生这个新的子序列。
- 与这个子序列在 第一次出现矛盾。
于是我们得到方程 。
用树状数组或前缀和优化即可。
100 pts
对于100%的数据,有 。
记 为 的前缀和 。
每次贪心选取使 最小即可。
时间复杂度 ,空间复杂度 。
很容易发现 与 有关,所有变量都可开成临时变量。内存可以优化为 。
- 1
信息
- ID
- 79
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 5
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者