咋做

原题链接：96793.Welcome24ever 和巧克力

༺ཌ融合版爱好者——改歌神ༀད༻

2026-01-24 12:18:51

发布于：浙江

26阅读

0回复

0点赞

没人对吗？我MLE了大家帮我看看怎么优化：

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    long long total_a = 1;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        if (total_a <= 1e12) total_a *= a[i]; // 防溢出
    }
    if (total_a < k) {
        cout << 0 << endl;
        return 0;
    }
    
    double logk = log(k);
    int M = 200000; // 离散化份数
    double step = logk / M;
    vector<double> dp(M+1, -1e100);
    dp[0] = 0;
    
    for (int i = 0; i < n; i++) {
        // 收集所有可能的 (b, x) 对
        vector<pair<double, double>> options; // (ln b, ln x)
        int ai = a[i];
        // 枚举 x
        for (int x = 1; x <= ai; x++) {
            int b = ai / x;
            if (b < 1) break;
            double lnb = log(b);
            double lnx = log(x);
            options.emplace_back(lnb, lnx);
            // 避免重复 b
            int b2 = ai / (x+1) + 1;
            if (b2 > b) continue;
            for (int bb = b2; bb < b; bb++) {
                int xx = ai / bb;
                if (xx == x) {
                    options.emplace_back(log(bb), log(xx));
                }
            }
        }
        // 去重相同的 lnb
        sort(options.begin(), options.end());
        options.erase(unique(options.begin(), options.end()), options.end());
        
        vector<double> ndp(M+1, -1e100);
        for (int j = 0; j <= M; j++) {
            if (dp[j] < -1e50) continue;
            for (auto [lnb, lnx] : options) {
                int idx = min(M, (int)((j*step + lnb) / step + 0.5));
                if (idx > M) idx = M;
                ndp[idx] = max(ndp[idx], dp[j] + lnx);
            }
        }
        dp = ndp;
    }
    
    double best = dp[M]; // 对应 ln b 和 >= log k
    if (best < -1e50) {
        cout << 0 << endl;
    } else {
        double prod_a = 0;
        for (int i = 0; i < n; i++) prod_a += log(a[i]);
        double ans = exp(best - prod_a) * k;
        cout << fixed << setprecision(12) << ans << endl;
    }
    
    return 0;
}