本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 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;
}