邮局选址问题

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n, m, l, r, s;
    cin>>n>>m;
    int a[n], dp1[n][n]={0}, dp2[m][n]={0}, b[m][n]={0};
    for(int i=0;i<n;i++)
        cin>>a[i];
    for(int i=0;i<n;i++){
        dp1[i][0] = 0;
        for(int j=i+1;j<n;j++)
            dp1[i][j] = dp1[i][j-1] + a[j] - a[(i+j)/2];
    }
    for(int i=0;i<n;i++){
        dp2[0][i] = dp1[0][i];
        b[0][i] = 0;
    }
    for(int i=1;i<m;i++){
        for(int j=n-1;j>i;j--){
            l = b[i-1][j];
            if(j==n-1)
                r = n-1;
            else
                r = b[i][j+1];
            dp2[i][j] = ~(1<<31);
            for(int k=l;k<=r;k++){
                s = dp2[i-1][k] + dp1[k+1][j];
                if(s <= dp2[i][j]){
                    dp2[i][j] = s;
                    b[i][j] = k;
                }
            }
        }
    }
    cout<<dp2[m-1][n-1]<<endl;
    return 0;
}

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int c = scanner.nextInt();
        int p = scanner.nextInt();
        int dp[][] = new int[c+1][p+1];//dp[i][j]在城市1-i建立j个站点所需的最少路径
        int dis[][] = new int[c+1][c+1];//dis[i][j] 表示在在城市i-j之间建立一个站点所需最少路程
        int city[] = new int[c+1];
        for (int i = 1; i <= c; i++) {
            city[i] = scanner.nextInt();
        }
        if(c<=p){//每个地方建一个
            System.out.println(0);
            return;
        }
        for (int i = 1; i <= c; i++) {
            for (int j = 0; j <= p; j++) {
                dp[i][j] = Integer.MAX_VALUE;//安装一个时选址一定在数组中心位置，偶数中心左右都可以
            }
        }
        for (int i = 1; i <= c; i++) {
            for (int j = i+1; j <= c; j++) {
                dis[i][j] = dis[i][j-1] + city[j] - city[i+ j >>1];//安装一个时选址一定在数组中心位置，偶数中心左右都可以
            }
        }
        dp[1][1] = 0;
        int [][]s = new int[c+2][p+2];//start[i][j]表示dp[i][j]最优时的下标k
        for (int i = 1; i <=c ; i++) {
             for (int j = p; j >=1  ; j--) {
                if (s[i][j + 1]==0)
                    s[i][j + 1] = i-1;//这里验算一下可以得出，max后会恒等于i - 1
                for (int k = s[i - 1][j]; k <= s[i][j + 1]; k++){
                    if (dp[i][j] - dis[k + 1][i] > dp[k][j - 1]  ){
                        dp[i][j] = dp[k][j - 1] + dis[k + 1][i];
                        s[i][j] = k;//更改最优决策

                    }
                }
            }
        }
        System.out.println(dp[c][p]);


    }
}

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));
        }
    }
}

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Main {
    // 题解：https://www.itdaan.com/blog/2017/11/12/363f67525ecbb9324ba4e1821281ab1b.html
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int num = sc.nextInt();

        int[] pos = new int[N];
        for (int i = 0; i < N; i ++) {
            pos[i] = sc.nextInt();
        }
        if (num >= N) {
            System.out.println(0);
            System.exit(0);
        }
        int[][] w = new int[N][N];
        // w[i][j] 表示 [i,j]上建立一个邮局，最短的总距离

        for (int i = 0;i < N; i ++) {
            w[i][0] = 0;
            for (int j = i + 1; j < N; j ++) {
                w[i][j] = w[i][j-1] + pos[j] - pos[(i + j) / 2];
            }
        }
        int[] dp = new int[N];
        int[] candi = new int[N];
        //dp[i][j]表示在[0,j]上建立i+1个邮局的最短总距离. dp[0][j] = w[0][j]
        for (int j = 0;j < N;j ++) {
            dp[j] = w[0][j];
        }
        for (int i = 1; i < num; i ++) {
            for (int j = N-1; j > i; j--) {
                int min = candi[j];
                int max = j == N - 1 ? j-1 : candi[j+1];
                int minValue = Integer.MAX_VALUE;
                for (int k = min;k < max + 1; k ++) {
                    int cur = Math.max(dp[k],w[k+1][j]);
                    if (cur <= minValue) {
                        minValue = cur;
                        candi[j] = k;
                    }
                }
                dp[j] = minValue;
            }
        }
        System.out.println(dp[dp.length-1]);
    }
}