小傑和奇犽來到了「天空鬥技場」,一座擁有 $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∣$$
小傑和奇犽以及兩部電梯最初都在天空鬥技場的 1 樓。小傑和奇犽必須精打細算,規劃出最佳的電梯移動路線,依序完成所有樓主的挑戰。
請你幫助小傑和奇犽,找出兩個人最少的念力消耗總和是多少。
輸入有兩行:
第一行包含五個整數 $N, A, B, C, D$,分別代表要經過的樓層數、以及能量計算公式中的常數。
第二行包含 $N$ 個整數 $F_1, F_2, \ldots, F_N$,代表依序要經過的指定樓層,保證數字不會重複。
輸出一個整數,代表挑戰完 $N$ 個樓層所需的最少念能力。
4 0 0 0 1 1 10 2 9
11
5 156 125 493 201 101818827 550809474 17607798 702981427 349052006
342962899286
一開始兩台電梯都停在1樓。第一筆測資中,最佳的行動方法如下:
總共花費:$0 + 9 + 1 + 1 = 11$
YTP 2025 高中組初賽 p5
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 |