ac

动态规划思路

如果只有1个画匠，负责arr[0...n-1]

如果有2个画匠，则1个负责arr[0...k], 令一个负责arr[k+1...n-1]，k取[0,n-1]
这么多方案中，找到 Min{ Max(sum[0...k], sum[k+1...n-1]) }即可

类似一个木头分成几段，尽量平均

dp[i][j]表示：i个画匠解决arr[0...j]

Min{ Max( sum[0...k], dp[i-1][k+1...j]) }

或者：

Min{ Max( dp[i-1][0...k]), sum[k+1...j] }

code

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[] sumTmp = new long[n+1];
        for(int i=0;i<n;i++){
            sumTmp[i+1] = arr[i] + sumTmp[i];
        }
        if(num == 1){
            return sumTmp[n+1];
        }
        if(n == 1){
            return arr[0];
        }
        long[][] dp = new long[num+1][n];
        for(int i=0;i<n;i++){
            dp[1][i] = sumTmp[i+1];
        }
        for (int i=1;i<=num;i++){
            dp[i][0] = arr[0];
        }
        for(int i=2;i<=num;i++){
            // i个画匠 解决arr[0...j]
            for(int j=1;j<n;j++){
                long minVal = Long.MAX_VALUE;
                for(int k=0;k<j;k++){
                    long left = dp[i-1][k]; // i-1 解决 arr[0...k]
                    long right = sumTmp[j+1] - sumTmp[k+1];  // arr[k+1...j] 作为右部分
                    minVal = Math.min(minVal, Math.max(left, right));
                }
                dp[i][j] = minVal;
            }
        }
        return dp[num][n-1];
    }
}
/*
3 2
3 1 4

4

5 3
1 1 1 4 3

4

5 2
99 82 44 35 3

164
 */

空间压缩

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[] sumTmp = new long[n+1];
        for(int i=0;i<n;i++){
            sumTmp[i+1] = arr[i] + sumTmp[i];
        }
        if(num == 1){
            return sumTmp[n+1];
        }
        if(n == 1){
            return arr[0];
        }
        // 1个工匠的情况
        long[] map = new long[n];
        for (int i=0;i<n;i++){
            map[i] = sumTmp[i+1];
        }
        // 2...num个工匠
        for(int i=2;i<=num;i++){
            // 解决arr[0...j]
            for(int j=n-1;j>=0;j--){
                if(j == 0){
                    map[j] = arr[0];
                }else {
                    long minVal = Long.MAX_VALUE;
                    for (int k = 0; k < j; k++) {
                        long left = map[k]; // i-1 解决 arr[0...k]
                        long right = sumTmp[j + 1] - sumTmp[k + 1];  // arr[k+1...j] 作为右部分
                        minVal = Math.min(minVal, Math.max(left, right));
                    }
                    map[j] = minVal;
                }
            }
        }
        return map[n-1];
    }
}
/*
3 2
3 1 4

4

5 3
1 1 1 4 3

4

5 2
99 82 44 35 3

164
 */

四边形不等式降低时间复杂度一个数量级

dp[i-1][j] 第 i-1 个工匠负责[l...j]是最优的
dp[i][j+1] 第 i 个工匠负责[m...j+1]是最优的
那么：dp[i][j] 第i个工匠负责[k...j], k应该属于[l...Math.max(m,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();
        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[] sumTmp = new long[n+1];
        for(int i=0;i<n;i++){
            sumTmp[i+1] = arr[i] + sumTmp[i];
        }
        if(num == 1){
            return sumTmp[n+1];
        }
        if(n == 1){
            return arr[0];
        }
        // 1个工匠的情况
        long[] dp = new long[n+1];
        dp[0] = 0;
        for (int i=0;i<n;i++){
            dp[i+1] = sumTmp[i+1];
        }
        // 存储 i-1 时最后一个工匠负责的范围, 与 dp[i] 对应
        int[] cands = new int[n+1];
        // 2...num个工匠
        for(int i=2;i<=num;i++){
            // 解决arr[0...j]
            for(int j=n-1;j>=0;j--){
                if(j == 0){
                    dp[j+1] = arr[0];
                    cands[j+1] = 0;
                }else {
                    long minVal = Long.MAX_VALUE;
                    int minPos = -1;
                    int kMin = cands[j+1];
                    int kMax = j == n-1 ? j : Math.min(cands[j+2], j);
                    for (int k = kMin; k <= kMax; k++) {
                        // 前i-1个工匠 解决 arr[0...k-1]
                        long left = dp[k];
                        // 第i个工匠 解决 arr[k...j]
                        long right = sumTmp[j + 1] - sumTmp[k];
                        long tmp = Math.max(left, right);
                        if(tmp <= minVal){
                            minVal = tmp;
                            minPos = k;
                        }
                    }
                    dp[j+1] = minVal;
                    cands[j+1] = minPos;
                }
            }
        }
        return dp[n];
    }
}
/*
3 2
3 1 4

4

5 3
1 1 1 4 3

4

5 2
99 82 44 35 3

164
 */

换个思路(二分法求解)

规定每个画匠的画画时间不能多余limit，那么需要几个画匠才能足够

利用二分法，调整limit

时间复杂度O(n * logSumArr)

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){
        if(n <= 0 || num <= 0){
            return -1;
        }
        long maxVal = Long.MIN_VALUE;
        long[] sumTmp = new long[n+1];
        for(int i=0;i<n;i++){
            sumTmp[i+1] = arr[i] + sumTmp[i];
            if(arr[i] > maxVal){
                maxVal = arr[i];
            }
        }
        if(num == 1){
            return sumTmp[n+1];
        }
        if(n <= num){
           return maxVal;
        }
        long ans = Long.MAX_VALUE;
        long min = 0;
        long max = sumTmp[n];
        while (min != max-1){
            long mid = (min + max) / 2;
            int res = getNeedNum(n, arr, mid);
            if(res == -1){
                // 需要提高 mid， 因为数组中有大于limit的了
                min = mid;
            }else {
                if(res > num){
                    // 需要增大limit,每个画匠多画点,以减少res
                    min = mid;
                }else {
                    ans = Math.min(ans, mid);
                    // 满足结果，看调小limit，让每个花匠少画点
                    max = mid;
                }
            }
        }
        return ans;

    }

    // limit需要多少个画匠
    static int getNeedNum(int n, long[] arr, long limit){
        int res = 1;
        long stepSum = 0 ;
        for(int i=0;i<n;i++){
            // 不满足最低limit的要求了
            if(arr[i] > limit){
                return -1;
            }
            stepSum += arr[i];
            if(stepSum > limit){ // 需要增加一个画匠了
                res ++;
                stepSum = arr[i];
            }
        }
        return res;
    }
}
/*
3 2
3 1 4

4

5 3
1 1 1 4 3

4

5 2
99 82 44 35 3

164
 */