日记

上午#

今天也是终于不用考试了。

CF2030E MEXimize the Score solution#

这题既然出现在了dp专题里，那就一定是dp咯
我们考虑每一个 $\min\limits_{k = 0}^{i}cnt_k$ 对答案的贡献是多少，也就是有多少个子序列满足 $\min\limits_{k = 0}^{i}cnt_k = j$ 。
我们设 $dp_{i,j}$ 表示只用了前 $i$ 个数（也就是 $[0,i]$ ），$\min\limits_{k = 0}^{i}cnt_k = j$ 的子序列数量。转移如下：

• 如果加入元素 $i$ 后，$\min\limits_{k = 0}^{i}cnt_k$ 才等于 $j$ ，则说明 $\min\limits_{k = 0}^{i - 1} > j$ 。那么我们就把大于 $j$ 的方案数之和，和从 $cnt_i$ 里取 $j$ 个的方案乘起来，有dp方程：$dp_{i,j} = \left(\sum\limits_{k = j + 1}^{cnt_i}dp_{i - 1,k} \right) \times \binom{cnt_i}{j}$ 。
• 如果加入元素 $i$ 后，$\min\limits_{k = 0}^{i}cnt_k$ 不变，还是 $j$ ，那么 $cnt_i \ge j$ 。我们就把 $i$ 的个数大于 $j$ 的组合数之和，和从前 $i - 1$ 个数里的方案数乘起来，有dp方程：$dp_{i,j} = \left(\sum\limits_{k = j}^{cnt_i}\binom{cnt_i}{k}\right) \times dp_{i - 1,j}$ 。

初始化的时候，$dp_{0,j} = \binom{cnt_0}{j}$ 。
然后如何统计答案呢？对于每一个 $dp_{i,j}$ ，我们只考虑了前 $i$ 个数，但是，后面的 $[i + 1,n)$ 我们没考虑。所以实际上，满足 $\min\limits_{k = 0}^{i}cnt_k = j$ 的子序列有 $dp_{i,j} \times 2^{\sum\limits_{k = i + 1}^{n - 1}cnt_k}$ 个。而答案又是 $j$ 乘子序列数量，那么总答案就是 $dp_{i,j} \times 2^{\sum\limits_{k = i + 1}^{n - 1}cnt_k} \times j$

剩下的不写了，明天的日记里再写。