Problem Summary: There are N houses, each of which contains some number of children, and in K of these N houses, there will be a school. The distance between house i and house j is abs(i — j). Then, each child will go to the nearest school to their house. Find the minimum total distance possible.

Naive DP: Let dp[i][j] = the min total distance for houses 0 to i, where there are exactly j schools in those houses, and the last house (house i) is guaranteed to be a school.

Then, the transition is dp[i][j] = min(dp[k][j — 1] + cost of children in houses k + 1 to i), where k < i. And to find the "cost of children in houses k + 1 to i" is easy, since we know that there is a school in both house k and house i. So, if you let m = (k + i) / 2, then you know that houses k + 1 to m will go to house k, and houses m + 1 to i will go to house i. Below is code for finding the cost of children in houses a + 1 to b:

int m = (a + b) / 2; // houses a + 1..m will go to house a, houses m + 1..b will go to house b
long long total_dist = 0;
for(int i = a + 1; i <= m; ++i) {total_dist += (long long) (i - a) * childs_at[i];}
for(int i = m + 1; i <= b; ++i) {total_dist += (long long) (b - i) * childs_at[i];}

This loop is O(b — a), but we can make it O(1). Use prefix sums over the childs_at[] array, and also keep another array child_val[] that stores i * childs_at[i] for each index i (and prefix sums over that array). Then,

total_dist += child_val_sum(a + 1, m) - a * childs_at_sum(a + 1, m);
total_dist += b * childs_at_sum(m + 1, b) - child_val_sum(m + 1, b);

So this gives a $$$O(N^2K)$$$ solution.

However, I'm not sure of how we can use the Convex Hull trick to optimize this DP. The transition I have currently comes out to be dp[i][j] = min(dp[k][j — 1] + copy-paste the formulas for calculating cost(k + 1, i). The main problem is the variable m, which is (i + k) / 2, since I don't know how to represent this as a linear function to use CHT on (for all the sums of subarrays, I tried splitting them up into prefix sums so we could represent the transition as a bunch of prefix sums, and some of the prefix sums require m as a variable, and I don't think it's possible to really represent this as a function of a single variable (since m = (i + k) / 2)).

Sorry is this is convoluted. Could someone confirm if my logic is correct, or if I'm missing something in this problem?

Note: I know that there's something called the "Divide and Conquer Optimization" that can be used to solve this problem. However, I want to try solving this with Convex Hull Trick for educational purposes. On this post at the USACO Guide Forum, it is said that CHT can be used to solve this problem: USACO Guide Link.