TopCoder

User's AC Ratio

NaN% (0/0)

Submission's AC Ratio

NaN% (0/0)

Tags

Description

小傑和奇犽來到了「天空鬥技場」,一座擁有 $10^ 9$ 層樓的高塔,每一層都會有一位樓主等著其他人來挑戰。以他們的實力,可以輕鬆打敗所有樓主。但是,想要快速晉級並賺取豐厚獎金,就必須高效利用競技場內僅有的兩部專用電梯。這些電梯由念能力驅動,每一次移動都會消耗使用者的念能力

小傑和奇犽從他們的師傅手中獲得了一份天空鬥技場的挑戰順序,他們一共要挑戰其中的 $N$ 個樓層,分別是 $F_1, F_2, \ldots, F_N$,每層樓最多挑戰一次。他們必須照這個順序到達各個樓層進行挑戰,挑戰 $F_{i+1}$ 層之前必須先挑戰完 $F_i$ 層。因為他們本身的實力強悍,只需要小傑和奇犽其中一位到達要挑戰的樓層即可完成挑戰。所以如何分配各個樓主的挑戰人選,來降低移動時的念能力的消耗就變得極其重要,電梯的念力消耗法則如下:

一台電梯從 $x$ 樓層移動到 $y$ 樓層 $(x \neq y)$,需要消耗 $f(x,y)$ 數量的念能力,遵循以下法則:

$$f(x,y)=A+B \cdot \max(0,y−x)+C \cdot \max(0,x−y)+D∣y−x∣$$

  • $A$:每次電梯被指令移動,都需要消耗的基礎念力。
  • $B \cdot \max(0,y−x)$:當電梯向上移動時,每層樓會額外消耗的念力。
  • $C \cdot \max(0,x−y)$:當電梯向下移動時,每層樓會額外消耗的念力。
  • $D∣y−x∣$:無論電梯向上或向下,每層樓都會累積消耗的念力。

小傑和奇犽以及兩部電梯最初都在天空鬥技場的 1 樓。小傑和奇犽必須精打細算,規劃出最佳的電梯移動路線,依序完成所有樓主的挑戰。

請你幫助小傑和奇犽,找出兩個人最少的念力消耗總和是多少。

Input Format

輸入有兩行:

第一行包含五個整數 $N, A, B, C, D$,分別代表要經過的樓層數、以及能量計算公式中的常數。

第二行包含 $N$ 個整數 $F_1, F_2, \ldots, F_N$,代表依序要經過的指定樓層,保證數字不會重複。

  • $1 \le N \le 3000$
  • $0 \le A, B, C, D \le 5000$
  • $1 \le F_i \le 10^ 9$,保證 $F_i$ 兩兩相異。
  • 所有輸入數字皆為整數。

Output Format

輸出一個整數,代表挑戰完 $N$ 個樓層所需的最少念能力。

Sample Input 1

4 0 0 0 1
1 10 2 9

Sample Output 1

11

Sample Input 2

5 156 125 493 201
101818827 550809474 17607798 702981427 349052006

Sample Output 2

342962899286

Hints

一開始兩台電梯都停在1樓。第一筆測資中,最佳的行動方法如下:

  • $F_1 = 1$,兩台電梯都在1樓,不用做任何移動就可以挑戰完畢,花費:$0$
  • $F_2 = 10$,移動其中一台電梯到10樓,花費: $|1-10| = 9$
  • $F_3 = 2$,移動原本在1樓的電梯,花費: $|1-2|=1$
  • $F_4 = 9$,移動原本在10樓的電梯,花費: $|10 - 9| = 1$

總共花費:$0 + 9 + 1 + 1 = 11$

Problem Source

YTP 2025 高中組初賽 p5

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測試資料 0
2 0~10 $1 \le N \le 18$ 3
3 11~19 $1 \le N \le 500$, $1 \le F_i \le 500$ 4.5
4 0~31 無額外限制 7.5

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 524288 65536 1 2 4
1 1000 524288 65536 1 2 4
2 1000 524288 65536 2 4
3 1000 524288 65536 2 4
4 1000 524288 65536 2 4
5 1000 524288 65536 2 4
6 1000 524288 65536 2 4
7 1000 524288 65536 2 4
8 1000 524288 65536 2 4
9 1000 524288 65536 2 4
10 1000 524288 65536 2 4
11 1000 524288 65536 3 4
12 1000 524288 65536 3 4
13 1000 524288 65536 3 4
14 1000 524288 65536 3 4
15 1000 524288 65536 3 4
16 1000 524288 65536 3 4
17 1000 524288 65536 3 4
18 1000 524288 65536 3 4
19 1000 524288 65536 3 4
20 1000 524288 65536 4
21 1000 524288 65536 4
22 1000 524288 65536 4
23 1000 524288 65536 4
24 1000 524288 65536 4
25 1000 524288 65536 4
26 1000 524288 65536 4
27 1000 524288 65536 4
28 1000 524288 65536 4
29 1000 524288 65536 4
30 1000 524288 65536 4
31 1000 524288 65536 4