백준15249 Building Bridges

작성일 | In

문제 링크

  • http://icpc.me/15249

문제 출처

  • 2017 CEOI Day2 1번

사용 알고리즘

  • CHT

시간복잡도

  • $O(N \log N)$

풀이

점화식을 세워봅시다.

$\displaystyle D_i = \min_{1 \leq j < i}(S_{i-1} - S_j + (H_i - H_j)^2 + D_j)$
$\displaystyle D_i = \min_{1 \leq j < i}(S_{i-1} - S_j + H_i^2 - 2H_iH_j + H_j^2 + D_j)$
$\displaystyle D_i = \min_{1 \leq j < i}(-2H_jH_i-S_j+H_j^2+D_j)+S_{i-1}+H_i^2$

min 안에 있는 식은 $H_i$에 대한 일차식입니다. 직선들이 여러 개 있을 때 최솟값은 Convex Hull Trick을 이용해 $O(\log N)$만에 구할 수 있습니다.

Convex Hull Trick에 직선을 $N$번 넣고 $N$번 쿼리를 날리므로 $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
51
52
53
54
55
56
57
58
59
60
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;

typedef long long ll;

struct Line{
    ll a, b;
    Line() : a(0), b(1e18) {}
    Line(ll a, ll b) : a(a), b(b) {}
    ll f(ll x){ return a*x+b; }
};
struct Node{
    int l, r; Line v;
    Node() : l(-1), r(-1) {}
};
vector<Node> tree;

void update(int node, ll s, ll e, Line v){
    Line lo = tree[node].v, hi = v;
    if(lo.f(s) > hi.f(s)) swap(lo, hi);
    if(lo.f(e) <= hi.f(e)){ tree[node].v = lo; return; }
    ll m = s + e >> 1;
    if(lo.f(m) < hi.f(m)){
        tree[node].v = lo;
        if(tree[node].r == -1) tree[node].r = tree.size(), tree.emplace_back();
        update(tree[node].r, m+1, e, hi);
    }
    else{
        tree[node].v = hi;
        if(tree[node].l == -1) tree[node].l = tree.size(), tree.emplace_back();
        update(tree[node].l, s, m, lo);
    }
}

ll query(int node, ll s, ll e, ll x){
    if(node == -1) return 1e18;
    ll res = tree[node].v.f(x), m = s + e >> 1;
    if(x <= m) return min(res, query(tree[node].l, s, m, x));
    else return min(res, query(tree[node].r, m+1, e, x));
}

ll n, h[101010], s[101010], dp[101010];
const ll inf = 1e12;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n;
    for(int i=1; i<=n; i++) cin >> h[i];
    for(int i=1; i<=n; i++) cin >> s[i], s[i] += s[i-1];
    tree.emplace_back(); update(0, -inf, inf, Line(-2*h[1], h[1]*h[1]-s[1]));
    for(int i=2; i<=n; i++){
        dp[i] = query(0, -inf, inf, h[i]) + h[i]*h[i] + s[i-1];
        update(0, -inf, inf, Line(-2*h[i], h[i]*h[i]-s[i]+dp[i]));
    }
    cout << dp[n];
}