백준 17526 - Star Trek (C++)

문제

• 문제 링크

  
   BOJ 17526 - Star Trek 
  

• 문제 요약

1에서 $n$으로 이동하려고 한다.
문제에 정의된 비용을 따를 때, 가장 최소의 비용으로 이동하는 경우를 구해보자.

• 제한

TL : $1$ sec, ML : $512$ MB




$3 ≤ n ≤ 100,000$

$1 ≤ s ≤ 100,000$

$0 ≤ p ≤ 1,000,000,000$

알고리즘 분류

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

풀이

임의의 지점으로 가는 데엔 결국 그 이전 지점들 중에 어디에서 환승하냐가 관건이다.
두 지점 간 거리를 빠르게 계산하기 위해 누적 합( $p[]$ )을 이용하자.
이후, 간단하게 점화식을 만들어 볼 수 있다.

$dp[i]$ : $1$ ~ $i$까지 이동하는 데에 드는 최소 비용

$dp[i] = min(dp[i], dp[j] + a[j] + b[j] * (p[i] - p[j]))$ {$1 ≤ j < i$}

---

$p[i] = x$로 하는 직선의 방정식으로 정리해보면

$f(x) = b[j] * x - b[j] * p[j] + a[j] + dp[j]$

CHT를 적용할 꼴이 나왔지만, 단조성이 딱히 없어 보인다.
따라서 리차오 트리를 이용해 각 $p[i]$에 대한 최솟값 쿼리를 날려주면 $O(NlogN)$으로 문제를 해결할 수 있다.

전체 코드

#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 M(1e18), c[N], dp[N];
int n, i, a[N], b[N];
 
void in()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    for (i = 2; i <= n; i++)
        cin >> c[i], c[i] += c[i - 1];
    for (i = 1; i < n; i++)
        cin >> a[i] >> b[i];
}
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)));
}
void sv()
{
    T.push_back({ -1, -1, 0, (ll)1e9, {0, M} });
    for (i = 2; i <= n; i++)
        push({ b[i - 1], dp[i - 1] + a[i - 1] - b[i - 1] * c[i - 1] }, 0), dp[i] = Q(c[i], 0);
    cout << dp[n];
}
int main()
{
    in();
    sv();
}

comment

이후 기여 탭에서 봤는데
식을 좀 더 잘 다듬어 보면, 단조성을 찾을 수 있다고 한다.