本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 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$ 次，答案式子的第一项的最大总和是多少。

$f_{i,j} = \max\limits_{x=0}^{\min(n,m)}{(g_{x,m}+\frac{n-x}{n}f_{i-1,j})}$。

时间复杂度是 $O(TKM^3)$ 的，听说有人用爆搜也过了。

Accepted Submission