题解 P3251 【[JLOI2012]时间流逝】

· · 题解

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

由于题面实在是太阅读理解了，我们先来提炼一个形式化的表述：给定 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;
}