第一章动态规划（十四）

斜率优化的DP

例题：300. 任务安排1

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

public class Main {
    static int N = 5010;
    static int INF = Integer.MAX_VALUE >> 1;
    static int n;
    static int s;
    static int[] sumt = new int[N];
    static int[] sumc = new int[N];
    static int[] f = new int[N];
    static int[] q = new int[N];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        s = sc.nextInt();
        for (int i = 1; i <= n; i++) {
            int t = sc.nextInt();
            int c = sc.nextInt();
            sumt[i] = sumt[i - 1] + t;
            sumc[i] = sumc[i - 1] + c;
        }
        Arrays.fill(f, INF);
        f[0] = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                f[i] = Math.min(f[i], f[j] + sumt[i] * (sumc[i] - sumc[j]) + s * (sumc[n] - sumc[j]));
            }
        }
        System.out.println(f[n]);
    }
}

例题：301. 任务安排2

加大了数据量，需要对上一题的方法进行优化。

import java.util.Scanner;

public class Main {
    static int N = 300010;
    static int n;
    static int s;
    static long[] t = new long[N];
    static long[] c = new long[N];
    static long[] f = new long[N];
    static int[] q = new int[N];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        s = sc.nextInt();
        for (int i = 1; i <= n; i++) {
            t[i] = sc.nextLong();
            c[i] = sc.nextLong();
            t[i] += t[i - 1];
            c[i] += c[i - 1];
        }
        int hh = 0, tt = 0;
        q[0] = 0;
        for (int i = 1; i <= n; i++) {
            while (hh < tt && (f[q[hh + 1]] - f[q[hh]]) <= (t[i] + s) * (c[q[hh + 1]] - c[q[hh]])) hh++;
            int j = q[hh];
            f[i] = f[j] - (t[i] + s) * c[j] + t[i] * c[i] + s * c[n];
            while (hh < tt && (f[q[tt]] - f[q[tt - 1]]) * (c[i] - c[q[tt - 1]]) >= (f[i] - f[q[tt - 1]]) * (c[q[tt]] - c[q[tt - 1]]))
                tt--;
            q[++tt] = i;
        }
        System.out.println(f[n]);
    }
}

例题 :302. 任务安排3

和 y总C++代码一样…有八个样例没通过

import java.io.*;

public class Main {
    static int N = 300010;
    static int n;
    static int s;
    static long[] t = new long[N];
    static long[] c = new long[N];
    static long[] f = new long[N];
    static int[] q = new int[N];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s1 = br.readLine().split(" ");
        n = Integer.parseInt(s1[0]);
        s = Integer.parseInt(s1[1]);
        for (int i = 1; i <= n; i++) {
            String[] s2 = br.readLine().split(" ");
            t[i] = Long.parseLong(s2[0]);
            c[i] = Long.parseLong(s2[1]);
            t[i] += t[i - 1];
            c[i] += c[i - 1];
        }
        int hh = 0, tt = 0;
        q[0] = 0;
        for (int i = 1; i <= n; i++) {
            int l = hh, r = tt;
            while (l < r) {
                int mid = l + r >> 1;
                if (f[q[mid + 1]] - f[q[mid]] > (t[i] + s) * (c[q[mid + 1]] - c[q[mid]])) {
                    r = mid;
                }else {
                    l = mid + 1;
                }
            }
            int j = q[r];
            f[i] = f[j] - (t[i] + s) * c[j] + t[i] * c[i] + s * c[n];
            while (hh < tt && (f[q[tt]] - f[q[tt - 1]]) * (c[i] - c[q[tt - 1]]) >= (f[i] - f[q[tt - 1]]) * (c[q[tt]] - c[q[tt - 1]]))
                tt--;
            q[++tt] = i;
        }
        System.out.println(f[n]);
    }
}

例题：303. 运输小猫

参考题解区- - -宇小苏

import java.util.*;

class Main {
    private static long INF = Long.MAX_VALUE;       //最大值不能再用0x3f3f3f3f了现在是long类型了
    private static long[] d, a, s;
    private static long[][] f;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int p = sc.nextInt();
        d = new long[n + 1];
        a = new long[m + 1];
        s = new long[m + 1];
        for (int i = 2; i <= n; i++) {
            d[i] = d[i - 1] + sc.nextInt();
        }

        for (int i = 1; i <= m; i++) {
            int h = sc.nextInt();
            int t = sc.nextInt();
            a[i] = t - d[h];
        }

        Arrays.sort(a, 1, m + 1);         //a中存在负数了，0不能参与排序的，所以从1 ~ m+1排序左闭右开
        for (int i = 1; i <= m; i++) s[i] = s[i - 1] + a[i];

        f = new long[m + 1][p + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 0; j <= p; j++) {
                f[i][j] = INF;
            }
        }
        int[] q = new int[m + 1];
        for (int j = 1; j <= p; j++) {
            int hh = 0, tt = -1;
            q[++tt] = (int) f[0][j];
            for (int i = 1; i <= m; i++) {
                while (hh < tt && (get_y(q[hh + 1], j) - get_y(q[hh], j)) <=
                        a[i] * (q[hh + 1] - q[hh])) hh++;
                int k = q[hh];
                f[i][j] = f[k][j - 1] + a[i] * (i - k) - (s[i] - s[k]);
                while (hh < tt && (get_y(i, j) - get_y(q[tt], j)) * (q[tt] - q[tt - 1]) <=
                        (get_y(q[tt], j) - get_y(q[tt - 1], j)) * (i - q[tt])) tt--;
                q[++tt] = i;
            }
        }
        System.out.println(f[m][p]);
    }

    private static long get_y(int k, int j) {
        return f[k][j - 1] + s[k];
    }
}