[ABC350E] Toward 0 讲解

zrl123456 · 2024-04-25 20:55:35 · 题解

题目

期望概率题目。
题目简述：
有两种选择：

花费 x 元把 n 变成 \lfloor\frac{n}{a}\rfloor。
花费 y 元，扔一次骰子得到一个数 p(1\le p\le 6)，把 n 变成 \lfloor\frac{n}{p}\rfloor。

求花费钱数的期望（不同操作得到的所有钱数的平均值），误差不大于 10^{-6}。

我们先往暴力的方向想，定义 f_i 表示 n=i 时的期望，按照题目中的意思写状态转移方程：

f_i=\begin{cases}0&i=0\\\min(f_{\lfloor\frac{i}{a}\rfloor}+y,\frac{\sum_{p=1}^{6}f_{\lfloor\frac{i}{p}\rfloor}}{6}+x)&otherwise\end{cases}

但是，f_i 又引用了 f_i，显然得不出正确答案，我们把式子变换一下：

\begin{aligned}\frac{\sum_{p=1}^6f_{\lfloor\frac{i}{p}\rfloor}}{6}+x&=\frac{\sum_{p=2}^6f_{\lfloor\frac{i}{p}\rfloor}}{6}+\frac{f_i}{6}+x\\&=\frac{6}{5}(\frac{\sum_{p=2}^6f_{\lfloor\frac{i}{p}\rfloor}}{6}+x)\\&=\frac{\sum_{p=2}^6f_{\lfloor\frac{i}{p}\rfloor}}{5}+\frac{6}{5}x\end{aligned}

这样我们就可以得到 f_i 了。

代码：

#include<bits/stdc++.h>
#define int long long
#define inl inline
#define INF LLONG_MAX
#define rep(i,x,y) for(int i=x;i<=y;++i)
#define rer(i,x,y,cmp) for(int i=x;i<=y&&cmp;++i)
#define per(i,x,y) for(int i=x;i>=y;--i)
#define FAST ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl '\n'
using namespace std;
int n,a,x,y;
map<int,double>mp;
inl double dfs(int n){
    if(n==0) return 0;
    if(mp[n]) return mp[n];
    double tmp=0;
    rep(i,2,6) tmp+=dfs(n/i);
    return mp[n]=min((tmp)/5.0+y/5.0*6,dfs(n/a)+x);
}
signed main(){
    FAST;
    cin>>n>>a>>x>>y;
    cout<<fixed<<setprecision(15)<<dfs(n);
    return 0;
}