ABC350E 题解

KSCD_ · 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;
}