luoguP4655 [CEOI2017]Building Bridges

斜率优化 + cdq分治

Building Bridges

思路

直接上 dp ，设 $d[i]$ 表示“连接 $1$ 和 $i$ 的最小代价” ，并令 $s[i]$ 表示 $w$ 的前缀和，那么有：
$$
d[i] = \min(d[j] + (h[i] - h[j])^2 + s[i - 1] - s[j])
$$
同样考虑决策 $j$ 优于 $k$ ，有：
$$
\begin{aligned}
d_j + (h_i - h_j)^2 + s_{i - 1} - s_j &< d_k + (h_i - h_k)^2 + s_{i - 1} - s_k \\
d_j + h_j^2 - 2h_ih_j - s_j &< d_k + h_k^2 - 2h_ih_k - s_k \\
\frac{(d_j + h_j^2 - s_j) - (d_k + h_k^2 - s_k)}{h_j - h_k} &< 2h_i
\end{aligned}
$$
发现 $h_j$ 和 $2h_i$ 都不单调，考虑 cdq 分治，先按 $2h_i$ 排序，每次先递归计算 $[l, mid]$ ，回来时把它们按 $h_j$ 排序，然后用 $[l, mid]$ 去跟新 $[mid + 1, r]$ ，再递归 $[mid + 1, r]$ 即可

时间 $O(n \log n)$

代码

一定要注意是 $p[i]$ 不是 $i$ ！一定要考虑 $X$ 相同的情况！

另外，实测加了 inline 的函数打法和 #define 的打法一样快

#include <bits/stdc++.h>
#define IL inline
// #define X(x) (h[x])
// #define Y(x) (d[x] + h[x] * h[x] - s[x])
// #define K(x) (2 * h[x])
using LL = long long;
const int N = 1e6 + 100;
const LL INF = 1e18;
int n;
int p[N], tmp[N], lp, rp, tp, q[N], ql, qr;
IL LL s[N], d[N], h[N]; 
IL LL X(int x){ return h[x]; }
IL LL Y(int x){ return d[x] + h[x] * h[x] - s[x]; }
IL LL K(int x){ return 2 * h[x]; }
IL bool cmp(int x, int y){ return X(x) == X(y) ? Y(x) < Y(y) : X(x) < X(y); }
IL void cdq(int l, int r)
{
    if (l == r) return ;
    int mid = (l + r) >> 1;
    lp = l - 1, rp = mid;
    for (int i = l; i <= r; ++i) (p[i] <= mid ? tmp[++lp] : tmp[++rp]) = p[i];
    for (int i = l; i <= r; ++i) p[i] = tmp[i];
    cdq(l, mid);
    ql = 1, qr = 0;
    for (int i = l; i <= mid; ++i)
    {
		if (i > l && X(p[i]) == X(p[i - 1])) continue;
        while (ql < qr && (Y(q[qr]) - Y(q[qr - 1])) * (X(p[i]) - X(q[qr])) >= (Y(p[i]) - Y(q[qr])) * (X(q[qr]) - X(q[qr - 1]))) --qr;
        q[++qr] = p[i];
    }
    for (int i = mid + 1, u, v; i <= r; ++i)
    {
        while (ql < qr && (Y(q[ql + 1]) - Y(q[ql])) < (X(q[ql + 1]) - X(q[ql])) * K(p[i])) ++ql;
        u = p[i], v = q[ql];
		d[u] = std::min(d[u], d[v] + (h[u] - h[v]) * (h[u] - h[v]) + s[u - 1] - s[v]);
    }
    cdq(mid + 1, r);
    lp = tp = l, rp = mid + 1;
    while (lp <= mid && rp <= r) tmp[tp++] = (cmp(p[lp], p[rp]) ? p[lp++] : p[rp++]);
    while (lp <= mid) tmp[tp++] = p[lp++];
    while (rp <= r) tmp[tp++] = p[rp++];
    for (int i = l; i <= r; ++i) p[i] = tmp[i];
}
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%lld", &h[i]), p[i] = i;
    for (int i = 1; i <= n; ++i) scanf("%lld", &s[i]), s[i] += s[i - 1];
    std::sort(p + 1, p + n + 1, [&](int x, int y){ return K(x) < K(y); });
    for (int i = 2; i <= n; ++i) d[i] = INF;
    cdq(1, n);
    printf("%lld\n", d[n]);
    return 0;
}