為因應資訊化與數位化的發展趨勢，某市長想要在城市的一些服務點上提供無線網路服務，因此他委託電信公司架設無線基地台。某電信公司負責其中 $N$ 個服務點，這 $N$ 個服務點位在一條筆直的大道上，它們的位置(座標)係以與該大道一端的距離 $P[i]$ 來表示，其中 $i=0\sim N-1$。現在電信公司要架設恰好$K$個基地台，使得每個服務點都可以得到服務。(也就是與APCS基地台相同，要建$K$個基地台覆蓋所有點)
由於科技的進步，現在電信公司可以客製化的建造基地台，也就是每個基地台的覆蓋範圍可以不相等。建造一個覆蓋範圍(直徑)$L$的基地台需要$L^2$的費用。請問電信公司至少要花多少錢才能建恰好$K$個基地台並且使得每個服務點都可以得到服務？
每筆測資輸入有兩行，讀到EOF結尾。第一行是兩個正整數 $N$ 與 $K$，以一個空白間格。第二行 $N$ 個非負整數$P[0],P[1],....,P[N-1]$表示 $N$ 個服務點的位置，這些位置彼此之間以一個空白間格。請注意，這 $N$ 個位置並不保證相異也未經過排序。
$1\le K\le N\le 500$
$0\le P[i]\le 10^9$
單一測資點不超過$5$筆測資。
每筆測資輸出最少需要的花費。
5 2 5 1 2 8 7 5 1 5 1 2 8 7
10 49
如果有人想出$O(N\lg C)$的做法的話 <(_ _)>。
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |
|||||