백준 4787 - Covered Walkway (C++)

문제

• 문제 링크

  
   BOJ 4787 - Covered Walkway 
  

• 문제 요약

커버해야 하는 $n$개의 지점과 상수 $c$가 주어진다.
지점 $[x, y]$를 커버한다면 $c + (y - x)^2$의 비용이 발생할 때, 모든 지점을 커버하는 최소 비용을 구해보자.

• 제한

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




$1 ≤ n ≤ 10^6$

$1 ≤ c, n_i ≤ 10^9$

알고리즘 분류

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

풀이

우선 나이브하게 접근해보자.

$dp[i] :$ 첫번째 지점부터 $i$번째 지점까지 커버하는 데에 드는 최소 비용.

임의의 지점 $V_i$와 $1 ≤ j ≤ i$인 $V_j$에 대해

$dp[i] = min((V[i] - V[j])^2 + dp[j - 1] + c)$

이를 모든 $i$에 대한 $j$를 보면 $O(N^2)$이므로, 적절한 최적화가 필요 하다.

---

식을 좀 정리해보면,

$(V[i] - V[j])^2 + dp[j - 1] + c$ 에서

$V[i]^2 - 2*V[i]*V[j] + V[j]^2 + dp[j - 1] + c$

$V[i]$를 $x$로 하고 $V[i]^2 + c$를 상수 $C$로 보면

$f(x) = -2 * V[j] * x + V[j]^2 + dp[j - 1]$ $ + $ $C$

$CHT$를 적용할 전형적인 모양이 보인다.

단조 증가하는 교점의 좌표에 대해 이분 탐색을 적용해 문제를 $O(NlogN)$에 풀 수 있고, $Li-Chao$ $Tree$를 이용해도 될 듯 하다.

또한, $V[i]$가 단조 증가 하므로 스택을 이용해 적절히 선분 손절을 해주면 $O(N)$에 근사하게 문제를 풀 수도 있을 것 같다.

전체 코드

#include<bits/stdc++.h>
#define ll long long
using namespace std;
 
struct Line
{
    ll p, q;
    double d;
    bool operator<(ll x) { return d < x; }
};
inline double f(Line& l, Line& r) { return (r.q - l.q) / (l.p - r.p); }
 
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    for (ll n, c; cin >> n >> c, n;)
    {
        vector <ll> V(n);
        for (ll& i : V) cin >> i;
 
        vector <Line> ln(n + 1);
        ll ans{};
        for (ll i{}, j{}; i < n; i++)
        {
            Line t({ -2 * V[i], V[i] * V[i] + ans, 0 });
            while (j)
            {
                t.d = f(t, ln[j - 1]);
                if (t.d > ln[j - 1].d) break;
                j--;
            }
            ln[j++] = t;
 
            ll idx = lower_bound(ln.begin(), ln.begin() + j, V[i]) - ln.begin() - 1;
            ans = ln[idx].p * V[i] + ln[idx].q + V[i] * V[i] + c;
        }
 
        cout << ans << '\n';
    }
}

comment

끝