r638. P4. 寶石列車的運算師 - 高中生程式解題系統

內容

你是寶石列車的運算師，車廂上排列著 n 個寶石，每種寶石有價值。每個回合你可以選擇從序列左端或右端拿走一顆寶石並獲得其價值，但有個 twist：每取走一顆，之後剩下序列的每顆寶石價值會按比例衰減（乘以某固定因子 p/q，分數形式，最後取整為下個整數）。請計算在最佳策略下，先手能獲得的最大總值差（先手總值 - 後手總值）。

輸入說明

n
v1 v2 ... vn
p q

（價值初始為整數；每次取走後剩下每顆乘以 p/q（四捨五入向下floor），若 p/q = 1 則無變化）

1 ≤ n ≤ 2000
0 ≤ vi ≤ 10^9
0 ≤ p ≤ q ≤ 10^9（以整數表示比例）

輸出說明

先手可取得的最大「先手 - 後手」總值差。

範例輸入 #1

12
12 11 10 9 8 7 6 5 4 3 2 1
926871255 987459511

範例輸出 #1

測資資訊：

記憶體限制： 512 MB
不公開測資點#0 (4%): 1.0s , <1K
不公開測資點#1 (6%): 1.0s , <1M
不公開測資點#2 (4%): 1.0s , <1K
不公開測資點#3 (4%): 1.0s , <1M
不公開測資點#4 (4%): 1.0s , <1K
不公開測資點#5 (6%): 1.0s , <1M
不公開測資點#6 (6%): 1.0s , <1M
不公開測資點#7 (6%): 1.0s , <1M
不公開測資點#8 (4%): 1.0s , <1K
不公開測資點#9 (4%): 1.0s , <1K
不公開測資點#10 (4%): 1.0s , <1K
不公開測資點#11 (6%): 1.0s , <1M
不公開測資點#12 (6%): 1.0s , <1M
不公開測資點#13 (4%): 1.0s , <1M
不公開測資點#14 (6%): 1.0s , <1M
不公開測資點#15 (6%): 1.0s , <1M
不公開測資點#16 (6%): 1.0s , <1M
不公開測資點#17 (4%): 1.0s , <1M
不公開測資點#18 (6%): 1.0s , <1M
不公開測資點#19 (4%): 1.0s , <1K

提示：

(40%) n ≤ 500
(60%) 原題 n ≤ 2000

標籤:

Algorithm Challenge contest Zaim

出處:

[管理者：

chenwei98050 ... (陳維（Z）) ]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」