We have $n$ customers, $(x_1, \dots, x_n)$, sorted on the read line. For convenience, we also use $x_i$ to denote its coordinate on the line. We need to locate $m$ facilities on the real line. We note that these facilities can be located anywhere on the real line. Each facility $j\in [m]$ is associated with an entrance fee $f_j$, such as the ticket money for a swimming pool. Given a location profile $(y_1, \dots, y_m)\in \mathcal{R}^m$ for the facilities($(y_1, \dots, y_m)$ is not necessarily ordered), the cost for customer $i$ at facility $j$ is $c_{ij} = |x_i- y_j|+f_j$, which can be understood as the aggregate money of the travelling cost and the entrance fee when you taxi to a swimming pool and purchase a ticket to swim inside. And the customer will always choose the facility so as to minimize her cost.
Our goal is to find a location profile $(y_1, \dots, y_m)$ for the given $m$ facilities such that the total minimum cost
$$\sum_{i\in [n]}\min_{j\in [m]}c_{ij}$$ is minimized.
An easy but critical obserbation is that there is an optimal solution where each facility is located in the median agent of the continuous region of agents it serves. If we have identical entrance fees, we only need to find the optimal $m$ continuous partitions, which can be solved by dynamic programming in $O(mn^2)$. For the general case, similar DP algortihm runs in $O(2^mn^2)$. The algorithm, however, is exponential in $m$ and only makes sense after we've proved the problem is NP-hard. Another observation which may be helpful is that for if we have known the optimal $m$ continuous partitions, we just assign the facility of the $k$-th smallest entrance fee to the partition of the $k$-th most customers.
So is this problem NP-hard? Or is there an algorithm running in polynomial time?