r989. PG. 魔法少女サクラバエマ - 高中生程式解題系統

內容

世界各地的少女們與キュゥべえ簽訂契約，以實現自己的願望，作為交換，她們會成為魔法少女。她們所使用的魔法的形式和效果都深受願望的影響。魔法少女サクラバエマ是一位新晉魔法少女，她最近與キュゥべえ簽訂了契約。サクラバエマ的願望是 “拯救一位因意外失去手指功能、放棄音樂的男孩”，因此她創造的魔法方陣形狀如同排列成圓圈的音符。

サクラバエマ擁有 N 張音符，她將它們排列在一個轉盤上，創造出一個幻方。她可以自由地以任何順序排列這些音符。創造幻方需要消耗精神能量，消耗量取決於音符的排列方式，如下：

首先，定義一個由 M 個正整數組成的音樂美 S ₁ , …, S _M 。
每個音符都有一個音程，用從 1 到 M 的整數 K ₁ , …, K _N 表示。
兩個音符之間的斥力， 其音程分別為 a 和 b ( a ≤ b ) ，定義為 [( S _a + … + S _b ) / L ] ，其中 L 是輸入中給出的常數，對於實數 x ， [ x ] 表示不超過 x 的最大整數。
サクラバエマ消耗的精神能量是相鄰兩個音符之間排斥力的總和（共有 N 對）。

例如，如果你依序排列音高分別為 {100, 200, 300, 400, 500} 和 {1, 3, 5, 4} 的音符，創造一個幻方，那麼消耗的心理能量將是 37 (=[(100+200+300) / 99]+[(300+400+500) / 99]+[(500+400) / 99]+[(400+300+200+100) / 99]) 。

已知所使用的音程組合以及每個音程的音樂美感，求消耗的最小腦力。

輸入說明

輸入格式如下：

N M L
K₁ K₂ … K_N
S₁ S₂ … S_M

N 是サクラバエマ擁有的音符數量， M 是音樂美感值的數量， L 是用來決定排斥力的常數。

K 代表音符的音高，S 代表音樂的美感。

3≤N≤2,000
1≤M≤10⁵
1≤L≤10⁵
1≤K_i≤M
1≤S_j≤10⁵
所有輸入值均為整數。．

輸出說明

在一行中寫出消耗的最少腦力能量。

範例輸入 #1

4 5 99
1 4 5 3
100 200 300 400 500

範例輸出 #1

範例輸入 #2

3 1 99
1 1 1
100

範例輸出 #2

測資資訊：

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

提示：

標籤:

DP contest Zaim

出處:

[管理者：

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

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