問題概要

数直線上 (東西方向) に $N$ 個の町があり、それぞれの町の座標は $X_{i}$ である。町 1 から出発して、すべての町を訪れたい。次の 2 つの手がある。

東または西へ 1 移動する：コスト $A$
ある町から他の町へとテレポートする：コスト $B$

達成するための最小コストを求めよ。

制約

$2 \le N \le 10^{5}$
$1 \le A, B, X_{i} \le 10^{9}$
$X_{1} \lt X_{2} \lt \dots \lt X_{N}$

考えたこと

一見すると、取り得る手がとても多くて、何から考えたらよいのかわからなく思えてしまう......こういうときは、「移動方法に制限を加えて解いても良い」という感じの考察が有効であることが多い。

さて、一般に 4 つの町 A, B, C, D について、下図の上側のような移動をするとする (途中テレポートを使ってもよい)。これは、下側のような移動に置き換えても、少なくともコストが悪化することはないことが言える (途中テレポートがあっても)。

このような考察を繰り返すことにより、結局

「町 $1$ → $2$ → $3$ → ... → $N$ 」

の順序で進んでいけばよいことがわかる。

残り

ここまで来ればもう簡単だ。町 $i$ から町 $i+1$ へと移動するための最小コストは

min(A * (X[i+1] - X[i]), B)

と表せる。これを各 $i$ について合算すればよい。計算量は $O(N)$ となる。

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long N, A, B;
    cin >> N >> A >> B;
    vector<long long> X(N);
    for (int i = 0; i < N; ++i) cin >> X[i];
    
    long long res = 0;
    for (int i = 0; i + 1 < N; ++i) {
        long long diff = X[i + 1] - X[i];
        res += min(diff * A, B);
    }
    cout << res << endl;
}