DDOSvoid's Blog

Luogu P4655 [CEOI2017]Building Bridges

发表于 分类于
本文字数： 2k 阅读时长 ≈ 2 分钟

题目描述

https://www.luogu.com.cn/problem/P4655

简要题意：有 $n$ 根柱子，每根柱子高度为 $h_i$，如果要架桥在 $i$ 和 $j$ 两根柱子间，需要花费 $(h_i-h_j)^2$，同时会拆掉 $i$ 到 $j$ 之间所有其它柱子，拆掉第 $i$ 根柱子的代价是 $w_i$，求连通 $1$ 和 $n$ 的最小代价，需要注意任意两座桥不能相交除了端点之外的地方相交

$n\le 10^5,0\le h_i,|w_i|\le 10^6$

Solution

容易得到 $dp$ 方程，$f_i=min\lbrace f_j+(h_i-h_j)^2+s_{i-1}-s_j\rbrace $​

化成直线的形式，$f_i-s_{i-1}-h_i^2+2h_ih_j=f_j+h_j^2-s_j$​，其中 $y=f_j+h_j^2-s_j,x=h_j,k=2h_i,b=f_i-s_{i-1}-h_i^2$

注意到 $k>0$，但 $k$ 和 $x$ 都不递增，所以只能使用 $cdq$ 来维护下凸壳进行更新

注意到 $k$ 和 $x$ 是同一个数组，所以 $cdq$ 可以做到 $O(n\log n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <iostream>
#include <algorithm>
#define maxn 100010
#define ll long long
#define INF 1000000000000000000
using namespace std;

int n, L;

ll s[maxn], a[maxn], f[maxn];
inline ll X(int i) { return a[i]; }

inline ll Y(int i) { return f[i] + a[i] * a[i] - s[i]; }

pair<ll, ll> Q[maxn];
inline double slope(pair<ll, ll> x, pair<ll, ll> y) { return 1.0 * (x.second - y.second) / (x.first - y.first); }

int id[maxn];
void cdq(int l, int r) {
    if (l == r) return ; int m = l + r >> 1;
    stable_partition(id + l, id + r + 1, [& m](const int &u) { return u <= m; });
    cdq(l, m); int h = 1, t = 0; 
    for (int i = l, p = l; i <= m; i = p) {
        ll y = Y(id[i]);
        while (p <= m && X(id[i]) == X(id[p])) y = min(y, Y(id[p++]));
        while (h < t && slope(Q[t - 1], Q[t]) > slope(Q[t - 1], { X(id[i]), y })) --t;
        Q[++t] = { X(id[i]), y };
    }
    for (int i = m + 1; i <= r; ++i) {
        int p = id[i];
        while (h < t && slope(Q[h], Q[h + 1]) < 2.0 * a[p]) ++h;
        f[p] = min(f[p], Q[h].second - 2 * a[p] * Q[h].first + s[p - 1] + a[p] * a[p]);
    } cdq(m + 1, r);
    inplace_merge(id + l, id + m + 1, id + r + 1, [](const int &u, const int &v) { return a[u] < a[v]; });
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1, x; i <= n; ++i) cin >> x, s[i] = s[i - 1] + x;
    for (int i = 1; i <= n; ++i) id[i] = i; 
    fill(f, f + maxn, INF); f[1] = 0;
    sort(id + 1, id + n + 1, [](const int &u, const int &v) { return a[u] < a[v]; });
    cdq(1, n); cout << f[n] << "\n";
    return 0;
}