백준 15249 - Building Bridges (C++)

문제

• 문제 링크

  
   BOJ 15249 - Building Bridges 
  

• 문제 요약

$1$에서 $n$을 잇는 다리를 지어보려 한다.
문제의 비용 발생 정의를 따를 때, 최소로 연결하는 비용을 구해보자.

• 제한

TL : $3$ sec, ML : $128$ MB




$2 ≤ n ≤ 10^5$

$0 ≤ h_i ≤ 10^6$

$0 ≤ |w_i| ≤ 10^6$

알고리즘 분류

• 다이나믹 프로그래밍(dp)
• 볼록 껍질을 이용한 최적화(convex hull trick)

풀이

결국 임의의 위치 $i$까지 다리를 지으려면 $1$에서 바로 짓냐, $1$에서 중간 지점 $j$를 거치고 $j$에서 오냐 로 구분해 볼 수 있다. (단, $j$까지의 최소 비용이 계산 됐다는 가정 하에.)
$j$ ~ $i$에 존재하는 기둥들의 $Σw$ 만큼 비용이 발생 하는데 이를 빠르게 계산할 수 있도록 누적 합( $p[]$ )을 이용하자.

이를 이용해 간단히 점화식을 정리해보면 $dp[i]$ : $1$ ~ $i$까지 다리를 짓는 데에 드는 최소 비용 이라 할 때 $dp[i] = min(dp[i], dp[j] + p[i - 1] - p[j] + (h[i] - h[j])^2)$ { $1 ≤ j < i$ } 로 정리할 수 있다.
이를 모든 $i$에 대한 $j$를 돌아보면 $O(N^2)$.

---

위 식을 우선 정리해보자.

$dp[j] + p[i - 1] - p[j] + (h[i] - h[j])^2$
$= dp[j] + p[i - 1] - p[j] + h[i]^2 - 2 * h[i] * h[j] + h[j]^2$

$j$의 변화에 관찰 되므로 $j$가 포함된 항들을 앞으로 빼보면

$= -2 * h[i] * h[j] + h[j]^2 + dp[j] - p[j] + h[i]^2 + p[i - 1]$

$h[i]$를 $x$로 보고 $Δj$의 변화와 관련 없는 항들을 상수로 빼면 $x$에 대한 일차 함수

$f(x) = -2 * h[j] * x + h[j]^2 + dp[j] - p[j]$ 로 정리할 수 있다.

단조성이 딱히 없어 보인다. 리차오 트리를 이용해 $dp$ 값들을 빠르게 계산하자.

전체 코드

#include<bits/stdc++.h>
#define ll long long
#define N 100001
using namespace std;
 
struct L
{
    ll p, q;
    inline ll f(ll x) { return p * x + q; }
};
struct Node
{
    ll l, r, s, e;
    L ln;
};
vector <Node> T;
ll n, i(1), M(1e18), a[N], b[N], dp[N];
 
void push(L q, ll n)
{
    ll s(T[n].s), e(T[n].e), m((s + e) >> 1); L p = T[n].ln;
    if (p.f(s) > q.f(s)) swap(p, q);
    if (p.f(e) <= q.f(e)) { T[n].ln = p; return; }
    if (p.f(m) < q.f(m))
    {
        T[n].ln = p;
        if (!~T[n].r)
            T[n].r = T.size(), T.push_back({ -1, -1, m + 1, e, { 0, M } });
        push(q, T[n].r);
        return;
    }
    T[n].ln = q;
    if (!~T[n].l)
        T[n].l = T.size(), T.push_back({ -1, -1, s, m, { 0, M } });
    push(p, T[n].l);
}
ll Q(ll x, ll n)
{
    return !~n ? M : min(T[n].ln.f(x), Q(x, ((x << 1) <= T[n].s + T[n].e ? T[n].l : T[n].r)));
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    T.push_back({ -1, -1, 0, (ll)1e9, {0, M} });
    for (cin >> n; i <= n; cin >> a[i++]);
    for (i = 1; i <= n; i++) cin >> b[i], b[i] += b[i - 1];
    for (i = 2; i <= n; i++)
        push({ -2 * a[i - 1], a[i - 1] * a[i - 1] - b[i - 1] + dp[i - 1] }, 0), dp[i] = Q(a[i], 0) + a[i] * a[i] + b[i - 1];
    cout << dp[n];
}

comment

끝