本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-04-20 22:09:37

题意

有两种操作方式：第一种为把 $N$ 变为 $\lfloor \frac{N}{A}\rfloor$，代价为 $X$；第二种为把 $N$ 变为 $\lfloor \frac{N}{k}\rfloor$，代价为 $Y$，其中 $k$ 为掷骰子的结果，即从 $\{ 1,2,3,4,5,6\}$ 中等概率选取一个。求以最优方式操作时把 $N$ 变成 $0$ 的期望代价。

思路

设 $f_i$ 表示把 $i$ 变成 $0$ 的期望代价，显然有 $f_0=0$。

考虑状态转移。若使用第一种操作，则显然有 $f_i=X+f_{\lfloor \frac{N}{A}\rfloor}$。

若使用第二种操作，由于有六种等概率的情况，有 $f_i=Y+\frac{1}{6}\sum_{k=1}^6 f_{\lfloor \frac{N}{k}\rfloor}$，即$f_i=Y+\frac{1}{6}f_i+\frac{1}{6}\sum_{k=2}^6 f_{\lfloor \frac{N}{k}\rfloor}$。

移项得 $\frac{5}{6}f_i=Y+\frac{1}{6}\sum_{k=2}^6 f_{\lfloor \frac{N}{k}\rfloor}$，即 $f_i=\frac{6}{5}Y+\frac{1}{5}\sum_{k=2}^6 f_{\lfloor \frac{N}{k}\rfloor}$。

用以上两种方式中较小的代价转移即可，可以记忆化搜索，使用map记录状态。

代码

#include<iostream>
#include<map>
#define int long long
using namespace std;
int read()
{
	int s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9') { if(ch=='-') w=-1; ch=getchar();}
	while(ch>='0'&&ch<='9') { s=s*10+ch-'0'; ch=getchar();}
	return s*w;
}
int n,A,X,Y;
map <int,double> f;
map <int,bool> v;
double sol(int x)
{
	if(v[x]) return f[x];
	v[x]=1;
	if(!x) f[x]=0;
	else
	{
		double ta=sol(x\/A)+X,tb=Y*1.2;
		for(int i=2;i<=6;i++) tb+=sol(x\/i)\/5;
		f[x]=min(ta,tb);
	}
	return f[x];
}
signed main()
{
	n=read(),A=read(),X=read(),Y=read();
	printf("%.6lf",sol(n));
	return 0;
}