E. Toward 0

 

        从大规模向小规模，用记忆化搜索，只需要分好类，有哪几种搜法。

        期望实际上就是把每一种情况的答案答案都算出来，然后取个平均值 ，并不困难。

        f ( i ) = [ f ( i / 6 ) + f ( i / 5 ) + f ( i / 4 ) + f ( i / 3 ) + f ( i / 2 ) + f ( i / 1 ) ] / 6 + Y

        f ( i ) = [ f ( i / 6 ) + f ( i / 5 ) + f ( i / 4 ) + f ( i / 3 ) + f ( i / 2 ) ] / 5 + 1.2 * Y

        要把所有的 f [ i ] 都移到等号左边。

        记忆化搜索真的是个好东西，是正向思维，比 dp 简单很多，以后要多用，能搜就搜。

        记忆化搜索是带返回值的，输出的时候如果要带小数点，用 printf ( " %.15f ", ans )

 

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 5, INF = 1e18;int T, n, A, X, Y, cnt, ans;
map<int, double> mp;double dfs(int i)
{if (i == 0)return 0;if (mp.count(i) != 0)return mp[i];return mp[i] = min(dfs(i / A) + X, (dfs(i / 6) + dfs(i / 5) + dfs(i / 4) + dfs(i / 3) + dfs(i / 2)) / 5 + 1.2 * Y);
}signed main()
{cin >> n >> A >> X >> Y;printf("%.7f", dfs(n));return 0;
}