题解 | #邮局选址问题#

import java.util.Map;
import java.util.Scanner;

public class Main {

    private static int[][] getRecord(int[] arr) {
        int[][] record = new int[arr.length][arr.length];
        for (int i = 0; i < arr.length; ++i) {
            for (int j = i + 1; j < arr.length; ++j) {
                record[i][j] = record[i][j - 1] + arr[j] - arr[(i + j) >> 1];
            }
        }
        return record;
    }

    /**
     * 四边形不等式优化
     *
     * @param arr
     * @param m
     * @return
     */
    private static int solvePlus(int[] arr, int m) {
        if (arr == null || arr.length == 0) {
            return 0;
        }

        int n = arr.length;
        int[][] record = getRecord(arr);
        m = Math.min(n, m);
        int[][] dp = new int[n][m];
        int[][] choose = new int[n][m];

        for (int i = 0; i < n; ++i) {
            dp[i][0] = record[0][i];
            choose[i][0] = (i + 1)/ 2;
        }

        for (int i = 1; i < n; ++i) {
            for (int j = Math.min(m - 1, i); j >= 1; --j) {
                dp[i][j] = record[0][i];
                int up = j == Math.min(m - 1, i) ? i : Math.min(i, choose[i][j + 1]);
                int down = Math.max(1, choose[i - 1][j]);

                for (int s = up; s >= down; --s) {
                    if (dp[i][j] > dp[s - 1][j - 1] + record[s][i]) {
                        dp[i][j] = dp[s - 1][j - 1] + record[s][i];
                        choose[i][j] = s;
                    }
                }
            }
        }

        return dp[n - 1][m - 1];
    }

    
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            int n = in.nextInt();
            int m = in.nextInt();
            int[] arr = new int[n];
            for (int i = 0; i < n; ++i) {
                arr[i] = in.nextInt();
            }
            System.out.println(solvePlus(arr, m));
        }
    }
}