[ABC052D] Walk and Teleport
题意翻译
在东西方向延伸的直线上,有N个城市。城市坐标按从西到东递增。
你现在在某个城市里,想去其他所有的城市。移动的方法有以下两种。
一,在直线上按东西方向平移,每移动一个单位距离疲劳值加A
二,直接瞬移到某个坐标,并且疲劳值加B
请使用以上两种方式直到去完其他所有的城市,并求出最小的疲劳值。
**输入输出格式**
输入格式:
第一行三个数,即N,A,B,
第二行N个数,即X[1],X[2]...,X[N]。
输出格式:
输出最小的疲劳值。
**说明**
2<=N<=1e5
1<=Xi,A,B<=1e9且X(i)<X(i+1)
题目描述
[problemUrl]: https://atcoder.jp/contests/abc052/tasks/arc067_b
東西方向にのびる直線上に、$ N $ 個の町があります。 町には、西から順に $ 1 $ から $ N $ までの番号がついています。 直線上には座標が設定されていて、東に行くほど座標が大きくなります。 町 $ i $ の座標は $ X_i $ です。
あなたは今、町 $ 1 $ にいて、これからほかの全ての町を訪れたいです。 移動する手段は次の $ 2 $ 種類あります。
- 直線上を歩いて移動する。 東西どちらに歩いても、$ 1 $ 移動する度に疲労度が $ A $ 上がります。
- 好きな場所へテレポートする。 テレポートをすると、移動した距離によらず疲労度が $ B $ 上がります。
この $ 2 $ 種類の移動を繰り返して全ての町を最適に回った時、疲労度の上昇値の合計の最小値がいくつになるか求めてください。
输入输出格式
输入格式
入力は以下の形式で標準入力から与えられる。
> $ N $ $ A $ $ B $ $ X_1 $ $ X_2 $ $ ... $ $ X_N $
输出格式
全ての町を最適に回った時、疲労度の上昇値の合計の最小値がいくつになるかを出力せよ。
输入输出样例
输入样例 #1
4 2 5
1 2 5 7
输出样例 #1
11
输入样例 #2
7 1 100
40 43 45 105 108 115 124
输出样例 #2
84
输入样例 #3
7 1 2
24 35 40 68 72 99 103
输出样例 #3
12
说明
### 制約
- 入力は全て整数である
- $ 2≦N≦10^5 $
- $ 1≦X_i≦10^9 $
- 全ての $ i(1≦i≦N-1) $ について、$ X_i\ <\ X_{i+1} $ が成り立つ
- $ 1≦A≦10^9 $
- $ 1≦B≦10^9 $
### Sample Explanation 1
町 $ 1 $ から町 $ 2 $ まで $ 1 $ の距離歩いて移動したあと、町 $ 3 $ にテレポートし、そこから町 $ 4 $ まで $ 2 $ の距離歩いて移動すると、 疲労度の上昇値の合計が $ 2×1+5+2×2=11 $ になり、これが最小です。
### Sample Explanation 2
町 $ 1 $ から町 $ 7 $ まで歩き続けると、疲労度の上昇値の合計が $ 84 $ になり、これが最小です。
### Sample Explanation 3
どのような順番でもよいので、$ 6 $ 回のテレポートで全ての町を訪れると、疲労度の上昇値の合計が $ 12 $ になり、これが最小です。