大概是每天记录一点学到的东西的样子
希望能持续做下去，暑假的牛客也有很多没有完全总结的部分，最近会整理发布

模拟退火

随机化算法，根据温度来有概率地接受一个更劣的解作为答案，减少了陷入局部最优解的可能
温度越低，接受更劣解的概率越低

随机化算法运行更长的时间更容易得到最优解，因此一次更改尽可能低，例如 O(1)O(1) 或者 O(log⁡)O(\log)，这样就能运行足够多的次数

算法的目的是优化某个目标函数，以下的讲解基于最小化函数 f(x)
通常需要计算更改前后的目标函数差值 delta = f(before) - f(after), 因为接受的概率是 exp(delta / T)，因此退火的初温需要通过计算得出

可以先做 1e3 次左右随机更改，计算负的 delta 的绝对值均值，再计算初温 T0 = average_bad_delta / (-ln p)，其中 p 一般取 0.8~0.9
设能接受的最小的变差能量为 d_min，希望结束时接受这种变差的概率为 1e-6
那么 TE = d_min / (-ln 1e-6), v = pow(TE / T0, 1 / N)，则可以运行一共 N 次的随机

伪代码如下，其中 f() 的计算通常需要根据改动以低复杂度算出，方案的记录也最好以低复杂度形式记录，此处仅为示意

std::mt19937_64 rng(std::chrono::system_clock::now().time_since_epoch().count());
auto rndi32(int l, int r) {
    return std::uniform_int_distribution<int>(l, r)(rng);
}
auto rnd() { return std::uniform_real_distribution<double>(0, 1)(rng); }

// ...

constexpr int N = 2e7;
double T0 = avg_delta / -std::log(0.8);
double TE = d_min / -std::log(1e-6);
double v  = std::pow(TE / T0, 1.0 / N);

auto best = init;

for (double T = T0; T > TE; T *= v) {
    auto next = change(now);
    auto delta = f(now) - f(next);
    if (delta >= 0 || rnd() < std::exp(delta / T))
        now = next;
    if (f(now) < f(best)) best = now;
}

将 if (delta >= 0 || rnd() < std::exp(delta / T)) 一行更改即可得到其它随机化算法

  • if (true) 得到朴素随机，通常需要数学上严格证明随机选取 N 次得不到解的概率极大
  • if (delta >= 0) 得到爬山算法

斜率优化 dp

常见于以下形式 dp[i] = min_or_max { dp[j] + calc(i, j) }，其中 j 是枚举的决策点，且对于一个确定的 j, dp[j] + calc(i, j) 是关于 i 的一次函数
如果横坐标单调且直线的斜率单调，可以用单调队列解决 min_or_max 的求解

using Line = std::array<i64, 2>;
std::vector<i64> dp(n, 0);
std::deque<Line> q;

auto getln = [&](int j) {
    return Line {-2 * a * sum[j], dp[j] + a * sum[j] * sum[j] - b * sum[j] + sumg[j]};
};
auto val = [](const Line& line, i64 x) -> i128 {
    return (i128)(line[0]) * x + line[1];
};

/*
对于 k2 > k1, 如果目前的 x 已经有 l2 > l1，那么以后 l1 也不会成为候选项，所以 pop_front()
得到队列末尾的三条线 l1, l2, l3 有 k1 < k2 < k3 
那么 l1, l2 交点 k1x + b1 = k2x + b2 => (k2 - k1)x = b1 - b2 => x1 = (b1 - b2) / (k2 - k1)
l2, l3 => x2 = (b2 - b3) / (k3 - k2)
当目前 x1 <= x <= x2 的时候，l2 最大
所以 x1 > x2 的时候，l2 不可能最大，弹，即 (b1 - b2) * (k3 - k2) > (b2 - b3) * (k2 - k1)
*/
auto cond = [](const Line& l1, const Line& l2, const Line& l3) {
    return (i128)(l1[1] - l2[1]) * (l3[0] - l2[0]) > (i128)(l2[1] - l3[1]) * (l2[0] - l1[0]);
};

q.push_back(Line {0, 0});
for (int i = 0; i < n; ++i) {
    i64 s = /* 横坐标取值，一个与 i 有关的量 */;
    while (q.size() >= 2 && val(q[0], s) <= val(q[1], s))
        q.pop_front();
    dp[i] = /* 与 i 有关的量或者常数 */ + val(q.front(), s);
    auto ln = getln(i);
    while (q.size() >= 2 && cond(q[q.size() - 2], q.back(), ln))
        q.pop_back();
    q.push_back(std::move(ln));
}

std::cout << dp[n - 1] + sumg[n - 1] << "\n";

如果没有两个单调性，需要使用李超线段树来快速求解横坐标处的最大取值

题单 https://www.luogu.com.cn/training/686472#problems

区间 dp

常见于合并问题，比如要相邻合并，最后求 [1, n] 合并成一个的代价最值的那种
设 dp[l][r] 为区间 [l, r] 的答案，则有转移方程

dp[l][r] = max_k[l, r] { dp[l][k] + dp[k+1][r] + merge([l, k], [k+1, r]) }

大概是 O(n3)O(n^3) 的，如果可以进行四边形不等式优化可以缩减到 O(n2)O(n^2)
四边形不等式还没完整地学，可能在后面会写

如果并不需要合并为一个点，则相当于划分 dp，如果用区间的方法做了也还需要一次前缀最优的划分

best[i] = max_j[0, i-1] { best[j] + dp[j+1][i] }

划分 dp

设 dp[i] 为前缀 i 的答案，则 dp[i] 可以由 dp[j] 加上一次 [j+1, i] 的划分转移得来

dp[i] = max_j[0, i-1] { dp[j] + calc(j+1, i) }

有可能可以使用斜率优化