C++ Weekly Practice (27) Recursion Algorithm Problem

Problem: Building Primary Schools in Mountainous Areas

[Problem Description]

The government has constructed a road in a mountainous area that passes through a total of m villages, visiting each village exactly once, without loops or intersections, and any two villages can only be accessed via this road. The distance between any two adjacent villages is di (a positive integer), where 0<i<m. In order to improve the cultural quality of the mountainous area, the government has decided to select n villages from the m villages to build primary schools (assuming that 0<n≤m<500). Please determine which villages to build primary schools in such a way that the total distance from all villages to the nearest primary school is minimized, and calculate the minimum value.

[Input]

The first line contains m and n, separated by a space.

The second line contains m−1 integers, representing the distances between adjacent villages from one end to the other, separated by spaces.

For example:

10 3 2 4 6 5 2 4 3 1 3

This indicates building 3 primary schools in 10 villages. The distance from the 1st village to the 2nd village is 2, the distance from the 2nd village to the 3rd village is 4, the distance from the 3rd village to the 4th village is 6, …, the distance from the 9th village to the 10th village is 3.

[Output]

The minimum sum of distances from each village to the nearest school.

[Input Example]

10 2 3 1 3 1 1 1 1 1 3

[Output Example]

Analysis:

To solve this problem, we need to find several villages among the given ones to establish primary schools, such that the total distance from all villages to the nearest primary school is minimized. We can use dynamic programming combined with preprocessing techniques to efficiently solve this problem.

Methodology

Position Calculation: First, calculate the position coordinates of each village. Since the villages are arranged sequentially along the road, we can determine the position of each village through the prefix sum of the distances between adjacent villages.
Preprocessing Interval Distance Sum: Preprocess to find the minimum distance sum for all villages in any interval [i, j] when building one primary school. The optimal school location is the median of the interval (the median minimizes the distance sum).
Dynamic Programming: Use dynamic programming to find the optimal solution for building multiple primary schools. Define dp[i][j] as the minimum distance sum when building j primary schools for the first i+1 villages (numbered from 0 to i). The state transition equation is:dp[i][j] = min(dp[k][j-1] + cost[k+1][i]) (where k is the partition point, the first k+1 villages build j-1 primary schools, and the remaining k+1 to i build 1 primary school).

Reference Code:

#include &lt;iostream&gt;#include &lt;vector&gt;#include &lt;cmath&gt;#include &lt;climits&gt;using namespace std;int main() {    int m, n;    cin &gt;&gt; m &gt;&gt; n;    vector&lt;int&gt; d(m - 1);    for (int i = 0; i &lt; m - 1; ++i) {        cin &gt;&gt; d[i];    }    // Calculate the position coordinates of each village    vector&lt;int&gt; pos(m, 0);    for (int i = 1; i &lt; m; ++i) {        pos[i] = pos[i - 1] + d[i - 1];    }    // Preprocess cost[i][j]: minimum distance sum for building 1 primary school between villages i and j    int cost[505][505] = {0};    for (int i = 0; i &lt; m; ++i) {        for (int j = i; j &lt; m; ++j) {            int mid = (i + j) / 2; // Median position            int sum = 0;            for (int k = i; k &lt;= j; ++k) {                sum += abs(pos[k] - pos[mid]);            }            cost[i][j] = sum;        }    }    // Dynamic programming array, dp[i][j] represents the minimum distance sum for building j primary schools for the first i+1 villages (0~i)    int dp[505][505];    // Initialization: case of building 1 primary school    for (int i = 0; i &lt; m; ++i) {        dp[i][1] = cost[0][i];    }    // Recursively calculate the case of building j primary schools (j from 2 to n)    for (int j = 2; j &lt;= n; ++j) {        for (int i = j - 1; i &lt; m; ++i) { // Building j primary schools for the first i+1 villages, i must be at least j-1 (each primary school must cover at least 1 village)            dp[i][j] = INT_MAX;            // Iterate through all possible partition points k, building j-1 primary schools for the first k+1 villages, and building 1 primary school for the remaining k+1 to i            for (int k = j - 2; k &lt; i; ++k) {                if (dp[k][j - 1] != INT_MAX) { // Prevent invalid state (INT_MAX indicates unreachable)                    dp[i][j] = min(dp[i][j], dp[k][j - 1] + cost[k + 1][i]);                }            }        }    }    cout &lt;&lt; dp[m - 1][n] &lt;&lt; endl;    return 0;}

Code Explanation

Input Handling and Position Calculation: Read the number of villages m, the number of primary schools n, and the array of distances between adjacent villages d, and calculate the position of each village pos using prefix sums.
Preprocessing Interval Distance Sum cost: For each interval [i, j], find the median position mid, calculate the distance sum from all villages in that interval to mid, and store it in cost[i][j].
Dynamic Programming Initialization: dp[i][1] represents the minimum distance sum for building 1 primary school for the first i+1 villages, initialized directly with cost[0][i].
Dynamic Programming Recursion: For the case of building j primary schools (j ≥ 2), iterate through all possible partition points k, calculate the distance sum for building j-1 primary schools for the first k+1 villages and 1 primary school for the remaining interval, and update dp[i][j] with the minimum value.
Output Result: The final result is dp[m-1][n], which is the minimum distance sum for building n primary schools for the first m villages.