백준11475 Journey to the "The World's Start"

작성일 | In

문제 링크

  • http://icpc.me/11475

사용 알고리즘

  • DP
  • 파라메트릭 서치
  • 세그먼트 트리 / 덱

시간복잡도

  • $O(N \log^2 N)$ 또는 $O(N \log N)$

풀이

역방향으로 이동하면 항상 손해이므로 항상 번호가 증가하는 정류장만 방문한다고 가정해도 충분합니다. 지하철을 타고 이동하는 시간은 항상 $N-1$로 일정하므로 환승 시간을 최소화하는 문제라고 생각할 수 있습니다.
범위가 $r$인 카드는 $r-1$인 카드가 이동할 수 있는 범위를 포함합니다. 따라서 범위가 $r$인 카드의 가격을 $\min\left{ p_1, p_2, \cdots, p_r \right}$이라고 생각해도 됩니다. 이동 범위가 증가하면 가격이 단조 증가하고 소요 시간은 단조 감소하므로 이동 범위에 대한 파라메트릭을 시도할 수 있습니다.

이동 범위를 $R$로 제한된 상황에서의 최소 소요 시간은 동적 계획법을 이용해 계산할 수 있습니다. $i$번째 정류장까지 이동하는데 드는 최소 환승 시간을 $D(i)$라고 하면, $D(i) = \min_{i-R \leq j < i} D(j) + 1$이 성립합니다. 단순하게 계산하면 $O(N^2)$이지만 세그먼트 트리를 이용하면 $O(N \log N)$, 덱을 이용하면 $O(N)$에 계산할 수 있습니다.

결정 문제를 $O(N \log N)$ 또는 $O(N)$에 해결할 수 있으므로 전체 문제를 $O(N \log^2 N)$ 또는 $O(N \log N)$ 시간에 해결할수 있습니다.

전체 코드

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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr int SZ = 1 << 16;
constexpr ll INF = 0x3f3f3f3f3f3f3f3f;

ll N, K, Cost[SZ], Wait[SZ], D[SZ], T[SZ<<1];
void Update(int x, ll v){
    for(T[x|=SZ]=v; x>>=1; ) T[x] = min(T[x<<1], T[x<<1|1]);
}
ll Query(int l, int r){
    l |= SZ; r |= SZ; ll res = INF;
    while(l <= r){
        if(l & 1) res = min(res, T[l++]);
        if(~r & 1) res = min(res, T[r--]);
        l >>= 1; r >>= 1;
    }
    return res;
}

bool Check(int x){
    memset(T, 0x3f, sizeof T);
    Update(1, 0);
    for(int i=2; i<=N; i++){
        int l = max(1, i-x), r = max(1, i-1);
        D[i] = Query(l, r) + Wait[i];
        Update(i, D[i]);
    }
    return D[N] + N - 1 <= K;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> K;
    for(int i=1; i<N; i++) cin >> Cost[i];
    for(int i=2; i<N; i++) cin >> Wait[i];
    int l = 1, r = N - 1;
    while(l < r){
        int m = (l + r) / 2;
        if(Check(m)) r = m;
        else l = m + 1;
    }
    cout << *min_element(Cost+r, Cost+N);
}