画家木板分配问题

https://www.geeksforgeeks.org/painters-partition-problem/

我们必须绘制n个长度为{A1，A2 … An}的木板。有k画家可用，每个画家需要1单位时间来绘画1单位的木板。问题是找到获取的最短时间。这项工作是在以下条件下完成的：任何画家都只能绘制连续的木板部分，例如木板{2，3，4}或仅木板{1}或什么都不涂，而不是木板{2，4，5}。

方法一 : dp[ ][ ] 表示前 j 块木板，i 个人的最短时间。
dp[ i ][ j ] = min( dp[ i ][ j ] , max(dp[ i - 1 ][ k ] , sum (a, k + 1 , j )) ) ,(1 <= k <=j );
dp[ i ] 只与 dp[ i - 1] 有关

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define sf(n) scanf("%d",&n)
#define pf(n) printf("%d",n)
#define pfc(c) printf(c)
#define fi(i,s,t) for(int i=s;i<t;i++)
#define fd(s,t) for(int i=s-1;i>=t;i--)
#define mem(a,c) memset(a,c,sizeof(a))
const int INF=0x3f3f3f3f;
const int MAX=1000000+10; 
int t,n,m,a[MAX];
ll sum[MAX],dp[MAX],dp2[MAX],best;
int main(){
	freopen("in","r",stdin);
	sf(t);
	while(t--){
		sf(n);
		fi(i,0,n){
			sf(a[i]);
			sum[i] = a[i];
			if(i) sum[i] += sum[i-1];
		}
		sf(m);
		if(n<m) {
			pfc("-1\n");
			continue;
		}
		fi(i,0,n)
			dp[i] = sum[i];
		fi(i,2,m+1){
			fi(h,0,n) dp2[h] = dp[h];
			fi(j,0,n){
				best = INF;
				fi(p,0,j+1){
					best = min(best, max(dp2[p] ,sum[j] - sum[p]));
				}
				dp[j] = best;
			}
		}
		pf(dp[n-1]);pfc("\n");
	}
	return 0;
}

方法二：分治。
最后的结果属于 max( a[ i ] ) - sum( a[ i ] ) ,对于 mid 如果对于给定的 k 个画家不可行，则取更大值继续。

// Source code submitted by Gaurav on Q&A
#include<bits/stdc++.h>
using namespace std;

// function to check if it is possible to distribute pages
bool isPossible(int arr[], int n, int m, long long int curMin) {
    
    int studentsRequired = 1;
    int curSum = 0;
	
    for (int i = 0; i < n; i++) {       
        if (arr[i] > curMin) return false;          
        // check if current number of pages are greater 
        // than curr_min that means we will get the result 
        // after mid no. of pages 
        if (curSum + arr[i] > curMin) {            
            studentsRequired++;
            curSum = arr[i];
             // if students required becomes greater 
             // than given no. of students,return false 
            if (studentsRequired > m) return false;
        }
        else {
            curSum += arr[i];
        }
    }
    return true;
}
// function to find min number of pages
int solve(int arr[], int n, int m) {   

    long long sum = 0;
    // return -1 if no. of books is less than 
    // no. of students 
    if(n < m) return -1;   
    // Count total number of pages 
    for(int i = 0; i < n; ++i) sum += arr[i];
     
    long long start = 0;
    long long end = sum, mid;
    long long int ans = int(1e15);
    
    while(start <= end) {
        
        mid = (start + end) / 2;
        
        // check if it is possible to distribute 
        // books by using mid as current minimum 
        if (isPossible(arr, n, m, mid)) {

            // if yes then find the minimum distribution 
            ans = ans<mid? ans:mid;
            
            // as we are finding minimum and books 
            // are sorted so reduce end = mid -1 
            // that means 
                end = mid - 1;
        }
        
         // if not possible means pages should be 
         // increased so update start = mid + 1 
        else {
            start = mid + 1;
        }
    }

     // at-last return minimum no. of  pages 
    return ans;
    
}
int main() {
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        int A[n];
        for(int i=0;i<n;i++){
            cin>>A[i];
        }
        int m;
        cin>>m;
        cout << solve(A, n, m) << endl;
    }
    return 0;
}