思路
考虑直接做是简单的背包 \(\rm{dp}\)
如果我们不想使用高精度, 就必须找到一种优化方案
观察以下柿子
\[ \begin{gather*}
& \sqrt[\sum_{i \in \mathbb{S}} b_i]{\prod_{j \in \mathbb{S}} a_j} \\
=& \prod_{j \in \mathbb{S}} a_j^{\frac{1}{b_j}}
\end{gather*} \]
这是我们 \(\rm{dp}\) 的形态, 我们要把他优化到不使用高精度的形式
发现一个很凶的东西
\(\ln (x^y) = y \ln x\)
因此以上柿子可以被优化为
\[ \begin{gather*}
& \sqrt[\sum_{i \in \mathbb{S}} b_i]{\prod_{j \in \mathbb{S}} a_j} \\
=& \exp \left( \frac{1}{\sum_{i \in \mathbb{S}} b_i} \sum_{j \in \mathbb{S}} \ln a_j \right)
\end{gather*} \]
还能说啥啊, nb
实现
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <cstdio>using namespace std;const long long MAXB = 8000;
const long double INF = 1e18;int main() {// freopen("dp.in", "r", stdin);// freopen("dp.out", "w", stdout);long long n, l, r;scanf("%lld%lld%lld", &n, &l, &r);vector<long long> a(n), b(n);long long sum_b = 0;for (long long i = 0; i < n; i++) {scanf("%lld%lld", &a[i], &b[i]);sum_b += b[i];}// 限制总b和不超过rsum_b = min(sum_b, r);vector<long double> dp(sum_b + 1, -INF);dp[0] = 0.0;for (long long i = 0; i < n; i++) {for (long long j = sum_b; j >= b[i]; j--) {if (dp[j - b[i]] != -INF) {dp[j] = max(dp[j], dp[j - b[i]] + log(a[i]));}}}long double ans = -INF;for (long long i = l; i <= r; i++) {if (dp[i] != -INF) {long double val = exp((1.0/i)*dp[i]);ans = max(ans, val);}}printf("%.7Lf\n", ans);return 0;
}
总结
\(\ln\) 和 \(\exp\) 可以方便的将底数取 \(\ln\)