a549. CPE：Patches (UVa 12654)

題目描述

輪胎是一個周長 C 的圓，在若干位置有破洞。可使用長度 T1 或 T2 的補片，數量不限、不能剪裁，補片可跨越量測起點，也可重疊。每個洞都必須被覆蓋，費用與所用補片總長度成正比。求補好所有洞所需的最小總長度。若兩洞相距恰好 k，長 k 的補片可以同時覆蓋。

輸入格式

多組資料直到 EOF。每組第一行 N C T1 T2：1 ≤ N ≤ 1000、1 ≤ C ≤ 10^6、1 ≤ T1,T2 ≤ C。第二行給 N 個順時針距離 Fi，0 ≤ Fi ≤ C−1，表示各洞距離粉筆記號的位置。

輸出格式

每組輸出一行最小補片總長度。

來源：UVa 12654 — Patches。本敘述依原題規格重新撰寫。