BOJ 10713 기차 여행

기차 여행
(http://boj.kr/10713)

문제 설명이 복잡한데, 결국 각 철도에서 티켓을 사용할지 IC카드를 사용할지를 결정하는 문제이다.
뭐가 더 나은지 확인하려면 \(i\)번 철도를 사용한 횟수가 \(K_i\)라고 하면 \(\text{min}(A_i\,\times\,K_i, B_i\,\times\,K_i+C_i)\)의 합이 답이다.

나는 철도를 몇 번 사용하는지를 저번 글처럼 펜윅트리를 썼는데, 생각해보니 구해놓고 다시 업데이트할 일은 없으니 배열로 해도 된다.

#include <bits/stdc++.h>
 
int n, tree[100001], t[100001];
 
void update(int idx, int val) {
    if (idx == 0)
        return;
    while (idx <= n) {
        tree[idx] += val;
        idx += idx & -idx;
    }
}
 
int sum(int idx) {
    int ret = 0;
 
    while (idx > 0) {
        ret += tree[idx];
        idx -= idx & -idx;
    }
 
    return ret;
}
 
int main() {
    int m;
    long long ans = 0;
 
    scanf("%d %d", &n, &m);
 
    for (int i = 1;i <= m;++i) {
        scanf("%d", &t[i]);
 
        if (i > 1) {
            if (t[i - 1] < t[i]) {
                update(t[i - 1], 1);
                update(t[i], -1);
            }
            else {
                update(t[i], 1);
                update(t[i - 1], -1);
            }
        }
    }
 
    for (int i = 1;i <= n - 1;++i) {
        long long a, b, c, p = sum(i);
        scanf("%lld %lld %lld", &a, &b, &c);
        ans += std::min(a * p, c + b * p);
    }
 
    printf("%lld", ans);
 
    return 0;
}