2026-01-24 12:18:51
发布于：浙江
22阅读
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;
}
有帮助，赞一个