ABC404F 题解

__vector__ · 2025-05-03 23:41:14 · 题解

凭什么这题分值比差分约束板子的 G 低！我这种过 F 不过 G 的亏死了。

难点

拆答案的贡献。

做法

每次游戏都随机排列，意思其实就是每次游戏结束前，都得不到任何关于正确按钮的位置信息。

那么，值得用于决策的信息就只剩下了当前的正确选择次数，当前剩下的游戏次数。

首先，可以自然的想到定义 f_{i,j} 代表还剩下 i 次游戏可以玩，还需要选中 j 次正确按钮才可以获得最终胜利。

转移的话，考虑当前这次游戏怎么玩。

似乎不是很好设计策略，那么来分析一下答案的贡献组成。

本次游戏假设有 x 个按钮的选中次数不为 0，其中第 l 个按钮被选中了 c_l 次。

那么，每个按钮都有 \frac{1}{n} 的概率是正确的按钮，此时状态推进到 f_{i-1,j-c_l}，贡献是 \frac{1}{n}f_{i-1,j-c_l}。

有 \frac{n-x}{n} 的概率所有 x 个按钮都不是正确的按钮，贡献是 \frac{n-x}{n}f_{i-1,j}。

所以，一种方案的答案就是 \frac{1}{n}\sum\limits_{l=1}^n f_{i-1,j-c_l}+\frac{n-x}{n}f_{i-1,j}。

可以看出来，答案跟选择的按钮数量，每个被选择的按钮的操作次数有关，而且每个按钮的贡献都是独立的，可以累加。

由此，可以对答案的第一项进行 dp，按钮数量也需要加入状态。

令 g_{i,j} 表示选择了 i 个按钮，总共用了 j 次操作，且每个按钮至少操作 1 次，答案式子的第一项的最大总和是多少。