# 【2018 ACM-ICPC 亚洲 南京区域赛】Tournament / 题解

Posted on

### Description

There are $N$ villagers (including the village chief) living in Number Village. Interestingly, all of their houses lie on a straight line. The house of the $i$-th villager $(0 ≤ i < N)$ lies exactly $a_i$ kilometers to the east of the village chief’s house. (For simplicity, the $0$-th villager is the village chief, so $a_0 = 0$.)Recently, a tournament is going to be held in Number Village, in which everyone in the village will participate. For the convenience of villagers, the organizer plans to build K stadiums. The stadium can be built anywhere in the village, even at the same place as any villager’s house.However, the organizer wants the traffic cost to be minimized. The traffic cost is defined by $\sum_{i=0}^{N-1}\min_{j=0}^{K-1}D(a_i,s_j)$, where $D(a_i, s_j)$ is the distance between the $i$-th villager’s house and the $j$-th stadium.Your task is to calculate the minimal traffic cost (rounded down to the nearest integer), given $N, K$ and $a_i$.

### Idea

$$f_{a,c}+f_{b,d}\leq f_{a,d}+f_{b,c}$$

$$dp_{j’}+f_{j’+1,i’}\leq dp_j + f_{j+1,i’}$$

$$dp_{j’}+f_{j’+1,i}\geq dp_j + f_{j+1,i}$$