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