abc350E Toward 0

给定整数N，每次可以选择支付X元将其除以A并向下取整，或者支付Y元掷筛子，假设点数为i，则将其除以i并向下取整，筛子每次都是等概率出现1-6。问将N变成0需要的最小花费的期望。
1<=N<=1E18; 2<=A<=6; 1<=X,Y<=1E9

分析：当前的期望是所有后续情况期望的概率加权。如果选择方案1，概率为1，花费为X；如果选择方案2，6种情况都对应1/6的概率，表示为dp[u] = (dp[u/1]+dp[u/2]+dp[u/3]+dp[u/4]+dp[u/5]+dp[u/6])/6 + Y，移项整理得dp[u]=(dp[u/1]+dp[u/2]+dp[u/3]+dp[u/4]+dp[u/5]+dp[u/6])/5 + 6Y/5，取二者的较小值作为u的最终期望。

#include <bits/stdc++.h>
using i64 = long long;

void solve() {
	i64 N, A, X, Y;
	std::cin >> N >> A >> X >> Y;

	std::map<i64,double> dp;

	auto dfs = [&](auto self, i64 u) -> double {
		if (u == 0) {
			return 0;
		}
		auto it = dp.find(u);
		if (it != dp.end()) {
			return it->second;
		}

		double &res = dp[u];
		double cost1 = X + self(self, u / A);
		double cost2 = 1.2 * Y;
		for (int i = 2; i <= 6; i++) {
			cost2 += 0.2 * self(self, u / i);
		}
		return res = std::min(cost1, cost2);
	};

	std::cout << dfs(dfs, N) << "\n";
}

int main() {
	std::cin.tie(0)->sync_with_stdio(0);
	std::cout << std::fixed << std::setprecision(10);
	int t = 1;
	while (t--) solve();
	return 0;
}