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).

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. I want to try solving with Convex Hull Trick for educational purposes. Here, it is said that CHT can be used to solve this problem: USACO Guide Link.