luogu link: https://www.luogu.com.cn/problem/P4677

Topic analysis: the first response is interval dp, which involves establishing schools in an uncertain interval to obtain the minimum distance.

So how do we consider this problem? Observe the data range: the maximum n is 500, and the three-layer for loop can be a

The routines of interval dp are relatively fixed, and there are three-level cycles: stage state decision: because there is no need to manage the left boundary when enumerating intervals, only one-level cycle is required. The second level cycle enumerates the number of schools to be established, and the third level cycle enumeration naturally establishes the location of schools in the interval.

In this way, we can roughly analyze the two-dimensional representation of the set: f[i][j] represents the minimum distance required to establish j schools in the first I villages and towns

We continue to analyze that since we want to divide the interval with k, the expression of the final distance should be the sum of the sub state after division and the distance in the interval after division.

So we can write the state transition equation: f[i][j] = f[k][j-1] + min(dis[k+1][i]);

Where min(dis(k+1,i)) means the minimum distance between k+1 and i

How to find this distance? Here we can use a little greed. If we want to minimize the distance in a fixed interval, the school must be built in the middle

When I first considered here, I was a little confused. If (interval left boundary + interval right boundary) is equal to an odd number, then divided by two, it must be the first of the two points in the middle. Can it be guaranteed to be the optimal solution?

For example: write the coordinates of four villages and towns directly here, 0,2,10,19. It is easy to know that the left boundary is 1, the right boundary is 4, and the midpoint gets the second point. Is the second point the same as the third point?

Similarly, when the second point is regarded as a school, the sum of the distances from other villages and towns to this point is set as s2. Similarly, s3 can be set

Then s2 = x2-x1+x3-x2+(x4-x3+x3-x2), s3 = x3-x2+(x3-x2+x2-x1)+x4-x3

It can be seen that if there are two midpoint, no matter which one is selected, the result is the same. Then we can rest assured to use the midpoint of the interval to build a school as the minimum value!

However, if we want to directly use dis[k+1][i] in the three-tier for loop, we need to initialize it first

That is, enumerate the left and right boundaries and midpoint respectively, and then accumulate to calculate dis[k+1][i]

    cin>>n>>m; 

	for(int i=2;i<=n;i++) //Since the prefix of the first topic is 0 and the second point is 0, the default is to accumulate from the first point 
	{
		cin>>a[i];
		a[i]+=a[i-1];
	}
	
	for(int l=1;l<=n;l++)           //Enumerate left endpoints 
		for(int r=l;r<=n;r++)       //Enumerate right endpoints 
		{
			int mid=(l+r)>>1;       //Fast bit operation 
			for(int k=l;k<=r;k++)   //Enumerate each village and town from left to right to accumulate the distance 
			dis[l][r]+=abs(a[mid]-a[k]);
		}

Then the core code is analyzed according to the state transition equation

dp[i][j]=min(dp[i][j],dp[k][j-1]+dis[k+1][i]);  //It means the scheme with the shortest distance to build j primary schools in the first i villages and towns

Obviously, k is the location of the enumeration to establish the primary school. Since I < j in the dp array is meaningless (meaning that there are fewer villages and towns than primary schools), the minimum value of k should start from j-1. So where does j start the cycle?

Since j-1 appears in the equation, j should start at least from 1. If I starts to cycle from 1, then dis[k+1][i] is 0 when k = 0 and i=0, which is legal, but dp[0][0]? It must also be 0

wait a second! We ignore one thing. Because the result requires a minimum value, the dp array cannot be initialized to 0 (it is equivalent to being initialized to 0 in the global), but should be initialized to positive infinity

So we need to initialize before writing the core code, but dp[0][0] must be 0

    memset(dp,0x3f3f3f3f,sizeof dp);
	
	dp[0][0]=0;
	
	for(int i=1;i<=n;i++)     //f[i][j] refers to j primary schools built in the first I villages, and k enumerates the locations 
		for(int j=1;j<=m;j++)
			if(j<=i)
			for(int k=j-1;k<=i-1;k++)dp[i][j]=min(dp[i][j],dp[k][j-1]+dis[k+1][i]);

Finally, submit the complete code~

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
const int N=510;
int n,m,a[N],dis[N][N],dp[N][N];
int main()
{
	cin>>n>>m; 
	for(int i=2;i<=n;i++) //Initialize the prefix and array. Since the title gives the distance, the coordinate of the first point is 0 by default and accumulated from the second point 
	{
		cin>>a[i];
		a[i]+=a[i-1];
	}
	
	for(int l=1;l<=n;l++)           //Enumerate left endpoints 
		for(int r=l;r<=n;r++)       //Enumerate right endpoints 
		{
			int mid=(l+r)>>1;       //Fast bit operation 
			for(int k=l;k<=r;k++)   //Enumerate each village and town from left to right to accumulate the distance 
			dis[l][r]+=abs(a[mid]-a[k]);
		}
		
	memset(dp,0x3f3f3f3f,sizeof dp);
	
	dp[0][0]=0;
	
	for(int i=1;i<=n;i++)     //f[i][j] refers to j primary schools built in the first I villages, and k enumerates the locations 
		for(int j=1;j<=m;j++)
			if(j<=i)
			for(int k=j-1;k<=i-1;k++)dp[i][j]=min(dp[i][j],dp[k][j-1]+dis[k+1][i]);

		
	printf("%d\n",dp[n][m]);
	return 0;
}