백준26647 알프스 케이블카 2

작성일 | In

문제 링크

  • https://icpc.me/26647

사용 알고리즘

  • Aliens Trick
  • DP

시간복잡도

  • $O(N \log N \log X)$

풀이

$D(k, n)$을 $k$개의 와이어를 사용해 $n$번째 산까지 연결하는 최소 비용이라고 정의합시다. $D(k, n) = \min_{1 \leq i < n} \left{ D(k-1, i) + C(i, n) \right}$ 형태로 나타낼 수 있고, $C(i, n) = (X_n-X_i)^2 + (Y_n-Y_i)^2$는 monge matrix이므로 aliens trick을 사용할 수 있습니다.

와이어를 하나 추가할 때마다 $\lambda$ 만큼의 추가 비용이 발생하는 상황에서, $n$번째 산까지 연결하는 최소 비용을 $D_\lambda(n)$이라고 정의합시다. $D(n) = \min_{1 \leq i < n}\left{ D(i) + C(i, n) + \lambda \right}$ 꼴로 나타낼 수 있고, $C(i, n) + \lambda$는 monge matrix이므로 monotone queue optimization을 사용할 수 있습니다.

따라서 전체 문제를 $O(N \log N \log X)$에 해결할 수 있습니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

template<class T, bool GET_MAX = false> // D[i] = func_{0 <= j < i} D[j] + cost(j, i)
pair<vector<T>, vector<int>> monotone_queue_dp(int n, const vector<T> &init, auto cost){
    assert((int)init.size() == n + 1); // cost function -> auto, do not use std::function
    vector<T> dp = init; vector<int> prv(n+1);
    auto compare = [](T a, T b){ return GET_MAX ? a < b : a > b; };
    auto cross = [&](int i, int j){
        int l = j, r = n + 1;
        while(l < r){
            int m = (l + r + 1) / 2;
            if(compare(dp[i] + cost(i, m), dp[j] + cost(j, m))) r = m - 1; else l = m;
        }
        return l;
    };
    deque<int> q{0};
    for(int i=1; i<=n; i++){
        while(q.size() > 1 && compare(dp[q[0]] + cost(q[0], i), dp[q[1]] + cost(q[1], i))) q.pop_front();
        dp[i] = dp[q[0]] + cost(q[0], i); prv[i] = q[0];
        while(q.size() > 1 && cross(q[q.size()-2], q.back()) >= cross(q.back(), i)) q.pop_back();
        q.push_back(i);
    }
    return {dp, prv};
}

ll N, K, X[50505], Y[50505];

pair<vector<ll>, vector<int>> Solve(ll c){
    auto cost = [c](int j, int i){ return (X[i] - X[j]) * (X[i] - X[j]) + (Y[i] - Y[j]) * (Y[i] - Y[j]) + c; };
    vector<ll> init(N+1, 1e18); init[0] = 0;
    return monotone_queue_dp<ll, false>(N, init, cost);
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> K; N--;
    for(int i=0; i<=N; i++) cin >> Y[i];
    for(int i=0; i<=N; i++) X[i] = (i ? X[i-1] : 0) + Y[i] * 2;
    for(int i=0; i<=N; i++) X[i] -= Y[i];

    ll l = 0, r = 1e14, res = -1e18;
    while(l <= r){
        ll m = (l + r) / 2;
        auto [dp,prv] = Solve(m);
        int cnt = 0; for(int i=N; i; i=prv[i]) cnt++;
        res = max(res, dp.back() - K*m);
        if(cnt <= K) r = m - 1; else l = m + 1;
    }
    cout << res;
}