1624 . 快樂設置道路
TopCoder
Tags
Description
傳說在ABCLS國中有兩個樹朋友的聚落, CKC, INF.
很巧的是, 這兩個樹朋友聚落的樹都排成一條直線.
而更巧的是, 這兩個聚落居然都是水平線!!
由於實在太神奇了, 兩邊聚落決定進一步加強友誼,
為此, 他們打算在兩邊各選出 k 棵樹, 並在之間建立道路.
不過, 為了道路施工的方便, 他們希望任兩條道路都不相交.
假設每建立 1 單位長的道路需要 c 元,
你能夠幫助他們算出, 至少需要多少元的預算嗎?
Input Format
第一行有五個自然數 n, m, k, c, d.
n 代表 CKC 聚落中有幾棵樹,
m 代表 INF 聚落中有幾棵樹,
d 表示兩個聚落的直線距離.
第二行有 n 個數字代表 CKC 聚落中的樹的 x 座標.
第三行有 m 個數字代表 INF 聚落中的樹的 x 座標.
(1 <= k <= n, m <= 400)
(1 <= c <= 100. 1 <= ni, mi, d <= 10000)
(保證任兩個 ni 不相同, 任兩 mi 也不相同)
Output Format
請輸出一個數代表至少需要多少預算.
(雖然樹朋友幣是可以有小數點的,
不過為了方便申請經費, 他們希望最後的總預算是整數.)
Sample Input 1
3 4 2 1 1
4 8 9
1 4 5 8
4 8 9
1 4 5 8
Sample Output 1
2
Hints
恩...為什麼圖片中INF的樹不是一條線呢?
其實是因為出題者畫完之後才發現這件事, 所以就不改了(?)
Problem Source
原TIOJ1624 / Problem Setter：worm
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 20 |
| 2 | 1 | 20 |
| 3 | 2 | 20 |
| 4 | 3 | 20 |
| 5 | 4 | 20 |