思路

考慮直接做是簡單的背包 \(\rm{dp}\)

如果我們不想使用高精度, 就必須找到一種優化方案
觀察以下柿子

這是我們 \(\rm{dp}\) 的形態, 我們要把他優化到不使用高精度的形式
發現一個很兇的東西
\(\ln (x^y) = y \ln x\)
因此以上柿子可以被優化為

還能說啥啊, 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和不超過r
    sum_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\)