90 邮局选址问题
Table of Contents

思路

第一行有两个整数N,num。分别表示居民点的数量，要建的邮局数量。
接下来一行N个整数表示邮局的坐标。保证坐标递增

6 2
1 2 3 4 5 1000

6
第一个邮局建立在3位置，第二个邮局建立在1000位置。那么1位置到邮局的距离为2,2位置到邮局距离为1,3位置到邮局的距离为0，4位置到邮局的距离为1,5位置到邮局的距离为2,1000位置到邮局的距离为0.
这种方案下的总距离为6。

数组是递增的，如下说明arr[i...j]选择中间点作为邮局距离是最短点

对于有偶数个，例如[4 15 26 47] 无论选择15还是26效果都是一样的，4个数值三个相邻距离设置为a b c

那么
15 作为邮局：a + b + (b + c) = a + 2b + c
 26 作为邮局：(a + b) + b + c = a + 2b + c

新增了一个数（不论原来是奇数个数，还是偶数个数）

[4 15 26 47] =》 [4,15,26,47,53]

a + 2b + c => a + 2b + c + (c+d) 比原来多了最后一个元素到中间点的距离

[4 15 26] =》 [4,15,26,47]

a + b => a + 2b + c 比原来多了最后一个元素到中间点的距离

所以有

w[i][j+1] = w[i][j] + arr[j+1] - arr[(i+j)/2]

对于一个元素的w[i][i]初始都是0

动归求解

dp[i][j]:表示arr[0...j]上设置i + 1个邮局，最后的总距离最短是多少

dp[2][5], 已知dp[1][5], 则有很多种选择

前两个邮局可以负责 arr[0..k],k属于[0....5]

dp[1][0] + w[1][5]
dp[1][1] + w[2][5]
.
.
.
dp[1][4] + w[5][5]
dp[1][5] + w[6][5]

dp[2][5] 等于所有方案的最小值即可

dp[i+1][j] = Min{ dp[i][k] + w[k][j] }

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static Scanner sc = new Scanner(System.in);

    public static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws Exception {
        int n = sc.nextInt();
        int num = sc.nextInt();
        int[] arr = new int[n];
        for(int i=0;i<n;i++){
            arr[i] = sc.nextInt();
        }
        System.out.println(solution(n, arr, num));
    }

    static long solution(int n, int[] arr, int num) {
        int[][] w = new int[n+1][n+1];
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                w[i][j] = w[i][j-1] + arr[j] - arr[(i+j)/2];
            }
        }

        int[][] dp = new int[num][n];
        // 1个邮局的情况
        for(int i=0;i<n;i++){
            dp[0][i] = w[0][i];
        }

        for(int i=1;i<num;i++){
            for(int j=0;j<n;j++){
                int minVal = Integer.MAX_VALUE;
                for(int k=0;k<=j;k++){
                    minVal = Math.min(minVal, dp[i-1][k] + w[k+1][j]);
                }
                dp[i][j] = minVal;
            }
        }
        return dp[num-1][n-1];
    }

}
/*
6 2
1 2 3 4 5 1000

6
 */

四边形优化时间复杂度

  1. 当邮局为a-1个,区间为arr[0...b]时，如果最优时1-a-2负责arr[0...l],a-1个邮局负责的是a[l+1...b]

那么

当邮局为a个,区间为arr[0...b]时，a-1个邮局不必尝试arr[0...l]小的区域了

  1. 当邮局为a个,区间为arr[0...b+1]时，如果最优时1-a-1负责arr[0...m],a个邮局负责的是a[m+1...b+1]

那么

当邮局为a个,区间为arr[0...b]时，a个邮局不必尝试比arr[0...m]大的区域了

即求dp[a][b]时，看dp[a-1][b]的a-2负责的位置，然后再看dp[a][b+1]的a-1负责的位置

ac代码

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static Scanner sc = new Scanner(System.in);

    public static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws Exception {
        int n = sc.nextInt();
        int num = sc.nextInt();
        long[] arr = new long[n];
        for(int i=0;i<n;i++){
            arr[i] = sc.nextLong();
        }
        System.out.println(solution(n, arr, num));
    }

    static long solution(int n, long[] arr, int num) {
        long[][] w = new long[n+1][n+1];
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                w[i][j] = w[i][j-1] + arr[j] - arr[(i+j)/2];
            }
        }

        long[][] dp = new long[num][n];
        int[][] s = new int[num][n];
        // 1个邮局的情况
        for(int i=0;i<n;i++){
            dp[0][i] = w[0][i];
            s[0][i] = 0;
        }

        for(int i=1;i<num;i++){
            for(int j=n-1;j>=i;j--){
                long minVal = Long.MAX_VALUE;
                int minPos = -1;

                int kMin = s[i-1][j];
                int kMax = j == n-1 ? j : s[i][j+1];
                for(int k=kMin;k<=kMax;k++){
                    if(dp[i-1][k] + w[k+1][j] <= minVal){
                        minVal = dp[i-1][k] + w[k+1][j];
                        minPos = k;
                    }
                }
                dp[i][j] = minVal;
                s[i][j] = minPos;
            }
        }
        return dp[num-1][n-1];
    }

}
/*
6 2
1 2 3 4 5 1000

6
 */

or

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static Scanner sc = new Scanner(System.in);

    public static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws Exception {
        int n = sc.nextInt();
        int num = sc.nextInt();
        long[] arr = new long[n];
        for(int i=0;i<n;i++){
            arr[i] = sc.nextLong();
        }
        System.out.println(solution(n, arr, num));
    }

    static long solution(int n, long[] arr, int num) {
        long[][] w = new long[n+1][n+1];
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                w[i][j] = w[i][j-1] + arr[j] - arr[(i+j)/2];
            }
        }

        long[][] dp = new long[num][n];
        int[] cands = new int[n];
        // 1个邮局的情况
        for(int i=0;i<n;i++){
            dp[0][i] = w[0][i];
        }

        for(int i=1;i<num;i++){
            for(int j=n-1;j>=i;j--){
                long minVal = Long.MAX_VALUE;
                int minPos = -1;

                int kMin = cands[j];
                int kMax = j == n-1 ? j : cands[j+1];
                for(int k=kMin;k<=kMax;k++){
                    if(dp[i-1][k] + w[k+1][j] <= minVal){
                        minVal = dp[i-1][k] + w[k+1][j];
                        minPos = k;
                    }
                }
                dp[i][j] = minVal;
                cands[j] = minPos;
            }
        }
        return dp[num-1][n-1];
    }

}
/*
6 2
1 2 3 4 5 1000

6
 */