백준 15249번 Building Bridges

문제 요약

기둥이 N개 있는데 각 기둥의 높이가 주어진다. 제일 왼쪽의 첫 기둥과 제일 오른쪽의 마지막 기둥을 이어주려고 한다.

각 기둥은 기둥을 무너뜨리는 데에 필요한 비용 $w_i$와 높이 $h_i$를 가지고 있다. i번재 기둥과 j번째 기둥을 잇는 데에 필요한 비용은 $(h_i-h_j)^2+(w_{i+1}+\cdots+w_{j-1})$이다.

첫 기둥과 마지막 기둥을 잇는 데 드는 비용의 최솟값을 구하시오.

N의 최댓값을 10만이다

풀이

다음과 같은 dp식을 유도하자.
$$
\begin{aligned}
dp(i) &= \text(1번 기둥부터 i번 기둥까지 이었을 때 최소비용) \
dp(i) &= \underset{j<i}{min}(dp(j)+(h_i^2-h_j)^2+p_{i-1}-p_j) \
dp(i) &= \underset{j<i}{min}(-2h_jh_i+h_j^2-p_j+dp(j))+h_i^2+p_{i-1}
\end{aligned}
$$
해당 dp식은 Convex Hull Trick을 통해서 $dp(N)$의 값을 $O(NlogN)$으로 구할 수 있다.

dp식 안에 있는 식의 기울기가 어떤 경향성도 지니지 않으므로 $O(N)$에 해결하는 것은 무리가 있어 보인다.

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

struct Line {
    mutable ll k, m, p;
    bool operator<(const Line& o) const { return k < o.k; }
    bool operator<(ll x) const { return p < x; }
};

struct LineContainer : multiset<Line, less<>> {
    // (for doubles, use inf = 1/.0, div(a,b) = a/b)
    const ll inf = LLONG_MAX;
    ll div(ll a, ll b) { // floored division
        return a / b - ((a ^ b) < 0 && a % b);
    }
    bool isect(iterator x, iterator y) {
        if (y == end()) { x->p = inf; return false; }
        if (x->k == y->k) x->p = x->m > y->m ? inf : -inf;
        else x->p = div(y->m - x->m, x->k - y->k);
        return x->p >= y->p;
    }
    void add(ll k, ll m) {
        auto z = insert({k, m, 0}), y = z++, x = y;
        while (isect(y, z)) z = erase(z);
        if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
        while ((y = x) != begin() && (--x)->p >= y->p)
            isect(x, erase(y));
    }
    ll query(ll x) {
        assert(!empty());
        auto l = *lower_bound(x);
        return l.k * x + l.m;
    }
};

int N;
ll h[100005], w[100005];
ll psum[100005];
ll dp[100005];

ll get_slope(int i) {
    return 2*h[i];
}

ll get_bias(int i) {
    return -(h[i]*h[i] - psum[i] + dp[i]);
}

ll get_sq(int i, int j) {
    return (h[i] - h[j]) * (h[i] - h[j]);
}

int main() {
    cin.tie(nullptr); ios::sync_with_stdio(false);
    cin >> N;
    for(int i=1;i<=N;++i) cin >> h[i];
    for(int i=1;i<=N;++i) cin >> w[i];
    for(int i=1;i<=N;++i) psum[i] = psum[i-1] + w[i];
    LineContainer min_hull;
    dp[1] = 0; min_hull.add(get_slope(1), get_bias(1));
    for(int i=2;i<=N;++i) {
        dp[i] = -min_hull.query(h[i]) + h[i]*h[i] + psum[i-1];
        min_hull.add(get_slope(i), get_bias(i));
    }
    cout << dp[N] << '\n';
    return 0;
}