自动搬运

查看原文

来自洛谷，原作者为

	MKCCT **

搬运于2025-08-24 21:46:58，当前版本为作者最后更新于2020-08-07 18:34:09，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

太菜了，大佬的题解都解释得比较简单，不太能看懂，于是就来写一篇友好一点的。

由于题面实在是太阅读理解了，我们先来提炼一个形式化的表述：给定 $n$ 种价值不同的元素，你需要维护一个可重集（开始是空集）。每一步你有 $p$ 的概率删除集合中一个价值最小的元素，如果当前是空集则这种情况概率为 $0$；否则你将等概率的获得一个元素，满足这个元素的价值不大于任何一个已经获得的元素的价值。求达到（或超过）给定的一个阈值 $T$ 所需的期望步数。

设 $f(S)$ 表示当前集合为 $S$ 时要达到目标的期望步数。记 $P$ 为达到当前状态的上一个状态集合，$\operatorname{suc}S$ 为 $S$ 的后继集合所组成的集族。

于是有转移：

$$f(S)=1+pf(P)+\frac{1-p}{|\operatorname{suc}S|}\sum_{V\in\operatorname{suc}S}f(V) $$

由之前的定义，显然 $S$ 的前驱 $P$ 是唯一的，等于 $S\setminus\{\min S\}$。如果我们将状态看作结点，转移关系看作边，那么整个转移过程形成了一个树形结构，前驱状态是父结点，后继状态是子结点。

这个转移显然是有后效性的，为了消去后效性，我们接下来将要证明：每个点的状态 $f(S)$ 都可以由父节点 $fa_S$ 表示成 $k_Sf(fa_S)+b_S$ 的形式，其中 $k_S,b_S$ 是对每个 $S$ 唯一的常数。

采用归纳法：对于叶结点，结论显然成立。现在考虑一个非叶结点。为了方便书写，记 $t=\frac{1-p}{|\operatorname{suc}S|}$，并将刚才转移中后面的那些状态用当前结点表示，有

$$f(S)=1+pf(P)+t\sum_{v\in\operatorname{suc}S}(k_Vf(S)+b_V) $$

再记

$$\sigma_k(S)=\sum_{V\in\operatorname{suc}S}k_V,\sigma_b(S)=\sum_{V\in\operatorname{suc}S}b_V $$

继续推刚才的式子：

$$\begin{aligned}&f(S)=1+pf(P)+t\sigma_k(S)f(S)+t\sigma_b(S) \\ \iff& (1-t\sigma_k(S))f(S)=pf(P)+1+t\sigma_b(S) \\ \iff& f(S)=\frac{p}{1-t\sigma_k(S)}f(P)+\frac{1+t\sigma_b(S)}{1-t\sigma_k(S)}\end{aligned} $$

这样便证明了当前结点也可用父结点表示，按照归纳假设，证毕。

结论证明了，做法也便明确了。我们可以按照树形 DP 那样 DFS，每次转移时维护结点的 $k,b$ 即可。最终答案就是 $f(\varnothing)$，也就是根节点的 $b$。每个状态的可重集只需用当前的价值和、已选元素的最小值构成的二元组来刻画。

代码短得离谱。

#include <bits/stdc++.h>
using namespace std;
typedef pair<double,double> pdd;

int n,T,a[55];
double p;

pdd dfs(int sum,int mn)
{
    if(sum>T) return make_pair(0,0);
    double k=0,b=0,t=(1-p)/mn;
    for(int i=1;i<=mn;++i)
    {
        pdd nxt=dfs(sum+a[i],i);
        k+=nxt.first,b+=nxt.second;
    }
    if(!sum) t=1.0/mn;
    return make_pair(p/(1-t*k),(1+t*b)/(1-t*k));
}

int main()
{
    while(~scanf("%lf%d%d",&p,&T,&n))
    {
        for(int i=1;i<=n;++i) scanf("%d",a+i);
        sort(a+1,a+n+1);
        printf("%.3f\n",dfs(0,n).second);
    }
    return 0;
}