백준 8571 - Apteka (C++)

문제

• 문제 링크

  
   BOJ 8571 - Apteka 
  

• 문제 요약

$N$명의 $C_i$값이 주어진다.
자리를 바꿀 때마다 문제에 정의된 데로 비용이 발생할 때, 맨 앞으로 가는 최소 비용을 구해보자.

• 제한

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




$1 ≤ N ≤ 10^6$

$1 ≤ C_i ≤ 10^9$

알고리즘 분류

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

풀이

   우선 문제를 다음과 같이 이해하면 편하다.

"$Hansel$의 위치가 $0$ 번 인덱스이고, $1, 2, ... N$번 인덱스 사람들의 $C_i$가 주어진다.
자리 스왑마다 $Hansel$과 $i$가 떨어진 거리 * $C_i$ 의 비용이 발생 한다고 할 때 $Hansel$이 $N$번째 자리에 도달할 수 있는 최소 비용은 ? "

---

다음과 같은 정의를 내려보자.

$dp[i]$ : $i$번째 위치에서 $N$번째 위치까지 도달하는 최소 비용.

그럼 이를 뒤에서부터 계산한다면 $i < j <= n$ 에서
$dp[i] = min(dp[i], (j - i) * a[j] + dp[j])$ 로 간단하게 점화식을 세워볼 수 있다.
이를 나이브하게 돌면 $O(N^2)$.


위 식에서 $i$를 $x$라 하면
$f(x) = -a[j] * x + j * a[j] + dp[j]$ 임에 따라
$-a[j]$의 기울기, $j * a[j] + dp[j]$의 절편을 갖는 직선의 방정식으로 나타낼 수 있다.
이제 컨벡스 헐 트릭을 적용할 수 있는 전형적인 형태가 보이니, 문제를 $O(N * logN)$에 해결할 수 있게 된다.

전체 코드

#include<bits/stdc++.h>
#define ll long long
#define N 1000001
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, M(1e18), a[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))); }
void sv()
{
    T.push_back({ -1, -1, 0, (ll)1e12, {0, M} });
    for (i = n - 1; !!~i; i--)
        push({ -a[i + 1], (i + 1) * a[i + 1] + dp[i + 1] }, 0), dp[i] = Q(i, 0);
    cout << dp[0];
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    for (cin >> n, i = 1; i <= n; cin >> a[i++]);
    sv();
}

comment

끝