给定整数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;
}
标签:std,double,self,i64,abc350E,auto,Toward,dp
From: https://www.cnblogs.com/chenfy27/p/18457331