Post office - post office issues (dynamic planning)

Post Office

Description
There is a straight highway with villages alongside the highway. The highway is represented as an integer axis, and the position of each village is identified with a single integer coordinate. There are no two villages in the same position. The distance between two positions is the absolute value of the difference of their integer coordinates.
Post offices will be built in some, but not necessarily all of the villages. A village and the post office in it have the same position. For building the post offices, their positions should be chosen so that the total sum of all distances between each village and its nearest post office is minimum.
You are to write a program which, given the positions of the villages and the number of post offices, computes the least possible sum of all distances between each village and its nearest post office.

Input
Your program is to read from standard input. The first line contains two integers: the first is the number of villages V, 1≤V≤300, and the second is the number of post offices P, 1≤P≤30, P≤V. The second line contains V integers in increasing order. These V integers are the positions of the villages. For each position X it holds that 1≤X≤10000.

Output
The first line contains one integer S, which is the sum of all distances between each village and its nearest post office.

Samples
Input Copy
10 5
1 2 3 6 7 9 11 22 44 50
Output
9

The main idea of the topic ：
There are several villages , Then I'm going to pick out a few to build a post office , The location of the village is on a number axis , The total distance from the village to the nearest post office should be minimized , Come up with a plan , Output the shortest distance .

Ideas ：
hypothesis n A village , build k individual , Then we convert it into a completed k-1 The smallest one , Then choose one of the rest to establish the minimum distance and .

Use two arrays to record ：
f[i][j] : yes 1-i A village , Established j The minimum consumption of a post office
w[i][j]： yes i-j The minimum cost of setting up a post office in the village

Here, please w Array optimization needs to be understood ：
If the original i and j There are even numbers between village, Suppose this time post office The construction address of is set to the position of the larger number in the median , At this time, new i after ,post office The position of the does not change , Then it is still calculated by the following formula :
w[i,j] =w[i,j-1]+a[i] - a[(j+i)/2]
· If the original i and j There are odd numbers between village（ namely （i+j）%2==0）, Add a new j after , You can still take the original K As the median , At this time, the median position remains unchanged , therefore
w[i,j] = w[i,j-1]+a[i] - a[(j+i)/2]

Here are the figures for understanding

So the optimized w[i,j] = w[i,j-1]+a[i] - a[(j+i)/2]

Last last f Array transfer equation ：
dp[i][j]=min(dp[i][j],dp[k][j-1]+w[k+1][i]);

AC Code ：

int a[maxn];
int w[400][400],dp[400][400];
int main(){
    
	int n = read() , m = read();
	for(int i=1;i<=n;i++) cin>>a[i];// Enter location , It is itself a prefix and 
	for(int i=1;i<=n;i++){
    
		for(int j=1+i;j<=n;j++){
    
			w[i][j]=w[i][j-1]+a[j]-a[(i+j)/2];
		}
	} 
	memset(dp,0x3f3f3f3f,sizeof(dp));
	for(int i=1;i<=n;i++) dp[i][i]=0,dp[i][1]=w[1][i];// It is equal when only one post office is established 
	for(int i=1;i<=n;i++){
    
		for(int j=2;j<=min(m,i);j++){
    // Number of post offices  
		//dp[i][j]=inf;
		for(int k=j;k<=i-1;k++){
    // Enumerate transferable locations , Of course, it is larger than the number of post offices  
                    dp[i][j]=min(dp[i][j],dp[k][j-1]+w[k+1][i]);
                }
		}
	}
	cout<<n<<" "<<m<<" "<<dp[n][m]<<"\n"; 
	for(int i=1;i<=n;i++) cout<<a[i]<<" ";
}

You can ask directly if you don't understand