백준10168 파발마

작성일 | In

문제 링크

  • http://icpc.me/10168

문제 출처

  • 2014 KOI 고등부 3번

사용 알고리즘

  • Convex Hull Trick
  • DP

시간복잡도

  • $O(N)$

풀이

원형을 처리하는 것은 언제나 귀찮기 때문에, 선형으로 바꿔서 풀이를 생각해봅시다.
상소문이 한양으로 가는 방법은 (1) $i, i-1, i-2, \cdots, 1$을 거쳐 한양으로 가는 것, (2) $i, i+1, i+2, \cdots, N$을 거쳐 한양으로 가는 것, 총 2가지가 있습니다.

풀이를 설명하기 전에 배열 $P, S$를 다음과 같이 정의하겠습니다.

  • $P_i = 1..i$번 지방에 있는 상소문의 개수 (Prefix Sum)
  • $S_i = i..N$번 지방에 있는 상소문의 개수 (Suffix Sum)

$D_i$를 $1..i$번 지방에 있는 상소문이 방법(1)을 이용해 한양으로 가는 최소 비용이라고 정의합시다.
상태 전이는 $j < i$인 $j$에 대해, $1..j$를 한양으로 잘 보낸 뒤, $j+1..i$를 묶어서 한 번에 한양으로 보내는 비용의 최솟값을 구하는 것입니다.

$1..j$를 한양으로 잘 보내는 최소 비용은 $D_j$만큼 걸리고, $j+1..i$를 묶어서 한 번에 한양으로 보내는 비용은 $(P_i - P_j + 1) \times i$입니다. 파말마를 $i$번 사용하고, $(P_i - P_j)$개의 상소문이 한양으로 들어가는데 $i$만큼의 시간이 걸리기 때문입니다.
따라서 DP 상태 전이를 식으로 표현하면 $D_i = \min_{0 \leq j < i}(D_j + (P_i - P_j + 1) \times i)$가 됩니다.

$j$에 대해 독립적인 항을 min 함수 밖으로 빼면 $D_i = \min_{0 \leq j < i}(-P_ji + D_j) + (P_i + 1) \times i$가 되고, min 함수 내부의 식이 일차 함수꼴이고 기울기와 쿼리 위치 모두 단조성이 있으므로 Convex Hull Trick을 이용해 $O(N)$에 점화식을 계산할 수 있습니다.

마찬가지로, $E_i$를 $i..N$번 지방에 있는 상소문이 방법(2)를 이용해 한양으로 가는 최소 비용이라고 정의합시다.
$E_i = \min_{i < j \leq N+1}(-S_j(N-i+1) + E_j) + (S_i+1) \times (N-i+1)$이 되고, 이것도 Convex Hull Trick을 이용해 $O(N)$에 계산할 수 있습니다.

문제의 정답은 $\min_{0 \leq i \leq N}(D_i + E_{i+1})$이 됩니다.

전체 코드

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
53
54
55
56
57
58
59
60
61
62
63
/******************************
Author: jhnah917(Justice_Hui)
g++ -std=c++17 -DLOCAL
******************************/

#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
#define IDX(v, x) lower_bound(all(v), x) - v.begin()
using namespace std;

using uint = unsigned;
using ll = long long;
using ull = unsigned long long;
using PLL = pair<ll, ll>;

struct CHT{
    vector<PLL> lines;
    int pv = 0;
    static ll f(const PLL &func, ll x){ return func.x * x + func.y; }
    bool bad(const PLL &a, const PLL &b, const PLL &c){
        return 1.0*(b.y-c.y)/(c.x-b.x) <= 1.0*(a.y-b.y)/(b.x-a.x);
    }
    void insert(ll a, ll b){
        while(lines.size() >= 2 && bad(lines[lines.size()-2], lines.back(), PLL(a, b))) lines.pop_back();
        lines.emplace_back(a, b);
    }
    ll get(ll x){
        while(pv+1 < lines.size() && f(lines[pv], x) >= f(lines[pv+1], x)) pv++;
        return f(lines[pv], x);
    }
};

int N, A[1010101];
ll S1[1010101], S2[1010101];
ll D1[1010101], D2[1010101];
CHT C1, C2;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N;
    for(int i=1; i<=N; i++) cin >> A[i];
    for(int i=1; i<=N; i++) S1[i] = S1[i-1] + A[i];
    for(int i=N; i>=1; i--) S2[i] = S2[i+1] + A[i];

    C1.insert(0, 0);
    for(int i=1; i<=N; i++){
        if(!A[i]){ D1[i] = D1[i-1]; continue; }
        D1[i] = C1.get(i) + (S1[i] + 1) * i;
        C1.insert(-S1[i], D1[i]);
    }
    C2.insert(0, 0);
    for(int i=N; i>=1; i--){
        if(!A[i]){ D2[i] = D2[i+1]; continue; }
        D2[i] = C2.get(N-i+1) + (S2[i] + 1) * (N-i+1);
        C2.insert(-S2[i], D2[i]);
    }
    ll mn = 0x3f3f3f3f3f3f3f3f;
    for(int i=0; i<=N; i++) mn = min(mn, D1[i] + D2[i+1]);
    cout << mn;
}