1730. 函数2

本蒟蒻想不出求精确解的方法。仅介绍求近似解的随机算法——模拟退火。

如果您有更好的解法或更好的实现欢迎评论区分享~

注意本题峰值太多,所以爬山算法不可用(爬山算法样例都过不了)

#include <bits/stdc++.h> using namespace std; #define sc(x) scanf("%lld", &x) typedef long long ll; typedef double db; ll a, b, c, d, e, l, r; db x, t, now, mx, ans = -6; db f(db x) { return sin(x / a) + sin(x / b) + sin(x / c) + sin(x / d) + sin(x / e); } void solve() { static ll rd = 1;//也可以用random_device生成种子 mt19937 mt(rd + time(0)); rd *= 2; uniform_real_distribution<db> dist0(0, 1); now = (l + r) / 2, t = r - l; while (t > 1e-6) { uniform_real_distribution<db> dist(-t, t); db newx = now + dist(mt); newx = max(1. * l, min(1. * r, newx)); db fnow = f(now), fnew = f(newx); db dt = (-fnew) - (-fnow); if (fnow < fnew || exp(-dt / t) > dist0(mt)) { now = newx; } if (ans < fnew) { ans = fnew; } t *= 0.999; } for (ll i = 0; i < 1000; ++i) //在终温随机多次 { uniform_real_distribution<db> dist(-t, t); db newx = now + dist(mt); newx = max(1. * l, min(1. * r, newx)); db fnow = f(now), fnew = f(newx); if (fnow < fnew) { now = newx; } if (ans < fnew) { ans = fnew; } } } signed main() { sc(a), sc(b), sc(c), sc(d), sc(e), sc(l), sc(r); for (ll i = 0; i < 20; ++i) //重要:多次退火 { solve(); } printf("%lf", ans); return 0; }

其他随机算法:遗传算法 (用的 python 所以看起来慢,可能用 C/C++ 跟模拟退火一样快)