AtCoder Beginner Contest 350 E - Toward 0
题意
给定四个数 N A X Y，你可以对 N 进行以下两种操作。
- 花费
X的代价将N变成 \(\lfloor \cfrac{N}{A} \rfloor\) - 花费
Y的代价掷一颗骰子，设掷出结果是i，将N变成 \(\lfloor \cfrac{N}{i} \rfloor\)
你需要执行若干次操作，每次操作可以选择上面两种中的一种。问将 N 变成 0 的最小花费。
题解
如果读者去在草稿纸上列公式，会发现一个问题：当投掷到 1 的时候，不太好讨论。我们定义一种状态，令 \(f(n)\) 表示将 n 变成 0 的最小花费。
于是对于每次操作，我们有两种策略：
- 选择花费
X，那么当前花费就是 \(f(n) = X + f(\lfloor \cfrac{n}{A} \rfloor)\) - 选择花费
Y，那么当前花费就是 \(f(n) = \cfrac{\sum_{i = 1}^6 (Y + f(\lfloor \cfrac{n}{i}) \rfloor)}{6}\)
所以有
\[f(n) = \min(X + f(\lfloor \cfrac{n}{A} \rfloor), \cfrac{\sum_{i = 1}^6 (Y + f(\lfloor \cfrac{n}{i}) \rfloor)}{6}) \]可以递归解决。
但是需要考虑到一种情况：当 \(i = 1\) 时，会无限递归，也就说有后效性。但是这个是只会出现在确实操作2才是最优操作时产生的，于是我们可以解方程。最后将第二种情况优化为
\[f(n) = \cfrac{6 \cdot Y + \sum_{i = 2}^6 f(\lfloor \cfrac{n}{i} \rfloor)}{5} \]那么就可以规避掉刚刚的情况了。代码不难写出
代码
#include <bits/stdc++.h>
#define endl '\n'
#define ls u << 1
#define rs u << 1 | 1
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
const int INF = 0x3f3f3f3f, N = 1e5 + 10;
const int MOD = 1e9 + 7;
const double eps = 1e-6;
const double PI = acos(-1);
inline int lowbit(int x) {return x & (-x);}
inline void solve() {
LL n, a, x, y;
cin >> n >> a >> x >> y;
map<LL, double> fn;
function<double(LL)> f = [&](LL v) {
if (v == 0) return 0.0;
if (fn.count(v)) return fn[v];
double t1 = (double)x + f(v / a);
double t2 = (double)y * 6;
for (int i = 2; i <= 6; i ++ ) t2 += f(v / i);
t2 /= 5;
return fn[v] = min(t1, t2);
};
cout << f(n) << endl;
}
signed main() {
#ifdef DEBUG
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
auto now = clock();
#endif
ios::sync_with_stdio(false), cin.tie(nullptr);
cout << fixed << setprecision(8);
int _ = 1;
// cin >> _;
while (_ -- )
solve();
#ifdef DEBUG
cout << "============================" << endl;
cout << "Program run for " << (clock() - now) / (double)CLOCKS_PER_SEC * 1000 << " ms." << endl;
#endif
return 0;
}