[JLOI2012]时间流逝

落日映苍穹つ 2021-12-23 15:27 178阅读 0赞

# [Luogu P3251 \[JLOI2012\]时间流逝 期望dp][Luogu P3251 _JLOI2012_ _dp] #

## 题目描述 ##

（简化版）

每天有两种情况。

1.每天，你可以（1-P概率）得到一个能量圈，但是对于新得到的相同的能量圈，它的能量不能大于你已拥有的任何一个能量（即小于等于最小的）

2.但是有时你会以P概率面对邪恶的果冻鱼，丢掉一个当前最小的能量圈

幸好，当你没有任何能量圈的时候，果冻鱼就算看见你也不会追着你，此时你可以好好地享用美食。

你听说当你的总的能量值超过了某个阈值之后，可以进化成强大模式并能够吃掉果冻鱼。是时候反击了！下面是本题的问题：预计要过多少天你才能进化成强大模式？（第一天默认你没有任何能量圈）

对于所有数据，0.1<=P<=0.9，1<=T<=50，1<=N<=50。

题解：

首先期望dp

其次，这个期望dp可以认为是一个起点，多个终点（即达到阈值），

一般用f\[s\]表示，能量圈**状态为s（状态具体处理再说）**，到终点的期望步数，然后通过f\[goal\]=0可以倒推。

这样，最后f\[1\]就是答案。

这个题目，对于确定的s，P概率丢掉唯一的一种情况返回上一级，

1-P概率获得一个能量圈，可能有多种情况。

一个点，多个儿子，一个父亲。

就是一个树形的转移了。

然后可以推f\[s\]的式子。

f\[s\]=p\*f\[last\[s\]\] + Σ(1-p)\*(1/sz)\*f\[son\] +1

但是这是个**环形的转移**。可以高斯消元

但是不够优秀。

套路地，

转化成线性的f\[s\]=k\*f\[last\[s\]\]+b;（k，b与s的儿子的k,b有关）

（式子看开头的博客，总之思路就是，假设有这个线性式子，把f\[soni\]=ki\*f\[s\]+bi代入，推出ks，bs和ki，bi的关系，发现确实是线性的，即可）

然而，虽然直观来看，我们还要求f\[last\[s\]\]，

但是发现f\[last\[初始\]\]=0，即初始因为不会丢掉能量圈

最终答案只和b，k有关。所以，我们只要通过这个线性式子，递推k，b即可。

最后的f\[s\]的b就是答案。

s怎么设计？

发现，为了知道丢哪个，必须记录最小的能量圈mi

因为是从起点往后推，所以不会出现丢掉最小值的难处理的问题。

发现，为了知道什么时候会超过阈值，必须知道当前的总能量e。

记录一下就好。

改成f\[i\]\[j\],b\[i\]\[j\],k\[i\]\[j\]记录f，b，k

因为e，mi相同，达到阈值的期望值就一定相同，可以记忆化一下，加快速度。

注意，起点只能得能量圈，所以不需要乘1-P到儿子了。

代码：

#include<bits/stdc++.h>
    using namespace std;
    const int N=53;
    double f[N][N];
    double b[N][N];
    double k[N][N];
    bool vis[N][N];
    int a[N];
    int n,t;
    double p;
    void dfs(int e,int mi){
        if(vis[e][mi]) return;
        vis[e][mi]=1;
        double sk=0.0,sb=0.0;
        
        for(int i=1;i<=mi&&e+a[i]<=t;i++){
            dfs(e+a[i],i);
            sb+=b[e+a[i]][i];
            sk+=k[e+a[i]][i];
        }
        //cout<<" e mi "<<e<<" "<<mi<<" : "<<sk<<" "<<sb<<endl;
        double c=(e==0)?1.00/((double)mi):(1.00-p)/((double)mi);
        k[e][mi]=p/((double)1-c*sk);
        b[e][mi]=(c*sb+1.00)/((double)1-c*sk);
    }
    int main()
    {
        while(scanf("%lf",&p)!=EOF){
            scanf("%d%d",&t,&n);
            memset(vis,0,sizeof vis);
            for(int i=1;i<=n;i++){
                scanf("%d",&a[i]);    
            }
            sort(a+1,a+n+1);
            dfs(0,n);
            printf("%.3lf\n",b[0][n]);
        }
        return 0;
    }

总结：关键点：

1.发现树形结构

2.列出转移方程。

环形的线性处理。起点的las一定是一个常数的，所以都可以算其他的k，b即可。

所以dp\[i\]其实设而不求。

转载于:https://www.cnblogs.com/Miracevin/p/9663263.html

[Luogu P3251 _JLOI2012_ _dp]: https://www.cnblogs.com/zykykyk/p/9454604.html