차례
문제 정책
Painter 's Partition 문제는 울타리가 있고 화가가 있다는 것을 말합니다. 우리는 화가가 모든 울타리를 칠하는 시간을 최소화하고 싶습니다. 화가가 울타리를 그리는 순서에는 한계가 있습니다. n 명의 화가가 있다고 가정하면 색인 'i'를 가진 화가는 연속적인 순서로만 울타리를 칠할 수 있습니다.
따라서 이것은 첫 번째 화가가 울타리 중 일부를 칠할 것임을 의미합니다. 그런 다음 두 번째 화가는 울타리 중 일부를 그립니다. 모든 화가에게도 마찬가지입니다. 이것은 일부 화가가 페인트 칠할 울타리조차 얻지 못하는 경우에 발생할 수 있습니다.
예
Size of fence : 10 40 40 10 Time of painting a unit length of fence : 1 Number of Painters : 2
50
설명 : 펜스 1과 2를 첫 번째 화가에게 할당하고 3, 4를 두 번째 화가에게 할당합니다. 첫 번째 화가에게 울타리 1 개를 할당하고 두 번째 화가에게 2, 3, 4를 할당했다면. 그런 다음 첫 번째 화가는 시간 = 10, 두 번째는 시간 = 90이 걸립니다. 모든 화가가 걸리는 최대 시간은 울타리를 칠하는 데 걸린 총 시간입니다. 이는 모든 화가가 동시에 그림을 그리기 시작하기 때문입니다. t = 0. 따라서이 이외의 방법은 더 나쁜 결과를 초래합니다.
Size of fence : 1 100 Time of painting a unit length of fence : 1 Number of Painters : 2
100
설명 : 울타리 1을 첫 번째 화가에게 할당하고 2를 두 번째 화가에게 할당합니다. 총 시간은 화가가 걸리는 최대 시간과 같기 때문입니다. 따라서 출력은 100입니다.
화가의 파티션 문제에 대한 접근
우리는 동적 프로그래밍 이 문제를 해결하기 위해. 여기서도 매우 잘 정의 된 동적 프로그래밍 O (1) 시간 복잡도에서 시간의 합을 취하는 기법 (접두사 합). 먼저 한 명의 화가의 문제를 해결하겠습니다. 그런 다음 화가 수 = 2, 3, 4,… n에 대해 상향식으로 해결합니다. i 번째 화가의 문제를 해결하기 위해 i 번째 화가가 울타리 k에서 j까지 페인트하는 데 걸린 시간을 찾을 수 있습니다. 여기서 우리는 i 번째 화가가 울타리 k에서 j까지 페인트하고 1부터 (k-1)까지의 울타리는 (i-1) 화가가 칠한다고 생각했습니다. 이 하위 문제에 대한 답은 (i-1) 화가 또는 i 번째 화가가 걸리는 최대 시간이어야합니다. 이런 식으로 우리는 더 작은 하위 문제를 계속해서 해결합니다. 그런 다음 이러한 작은 하위 문제의 결과를 결합하여 초기 문제 (페인터의 파티션 문제)를 해결합니다.
암호
C ++ 코드 화가의 파티션 문제
#include <bits/stdc++.h>
using namespace std;
long long int solvePaintersPartitionProblem(long long int numberOfPainters, long long int timePerUnit, vector<long long int>& fenceSize){
int numberOfFences = fenceSize.size();
if(numberOfFences == 0)return 0;
vector<long long int> pref(numberOfFences); // stores the prefix sum for faster sum calculation over the range
pref[0] = (fenceSize[0] * timePerUnit);
for(int i=1;i<numberOfFences;i++) {
pref[i] = (fenceSize[i] * timePerUnit);
pref[i] = (pref[i] + pref[i-1]);
}
long long int dp[numberOfPainters][numberOfFences]; // dp[i][j] = minimum time taken for painting j fences by i painters such that they can paint only in contiguous order
for(int i=0;i<numberOfPainters;i++){
for(int j=0;j<numberOfFences;j++)
dp[i][j] = LONG_MAX;
}
// Filling the values for first painter
for(int i=0;i<numberOfFences;i++)dp[0][i] = pref[i];
// Now solving for painters 2, 3, 4......n
for(int i=1;i<numberOfPainters;i++){
for(int j=i;j<numberOfFences;j++){
for(int k=i;k<=j;k++){
long long int timeTakenForithPainter = pref[j] - pref[k-1];
dp[i][j] = min(dp[i][j], max(dp[i-1][k-1], timeTakenForithPainter));
}
}
}
if(numberOfPainters > numberOfFences)return dp[numberOfFences-1][numberOfFences-1];
return dp[numberOfPainters-1][numberOfFences-1];
}
int main(){
int t;cin>>t;
while(t--){
long long int numberOfPainters, numberOfFences, timePerUnit;
cin>>numberOfPainters>>timePerUnit>>numberOfFences;
vector<long long int> fenceSize(numberOfFences);
for(int i=0;i<numberOfFences;i++) cin>>fenceSize[i];
long long int ans = solvePaintersPartitionProblem(numberOfPainters, timePerUnit, fenceSize);
cout<<ans<<endl;
}
}
2 2 5 2 // number of painters, time taken paint a unit length of fence and number of fences 1 10 // fences size 10 1 4 1 8 11 3
50 11
자바 코드 화가의 파티션 문제
import java.util.*;
import java.lang.*;
import java.io.*;
class Main {
static long solvePaintersPartitionProblem(int numberOfPainters, long timePerUnit, int numberOfFences, long fenceSize[]){
if(numberOfFences == 0)return 0;
long pref[] = new long[numberOfFences]; // stores the prefix sum for faster sum calculation over the range
pref[0] = (fenceSize[0] * timePerUnit);
for(int i=1;i<numberOfFences;i++) {
pref[i] = (fenceSize[i] * timePerUnit);
pref[i] = (pref[i] + pref[i-1]);
}
long dp[][] = new long[numberOfPainters][numberOfFences]; // dp[i][j] = minimum time taken for painting j fences by i painters such that they can paint only in contiguous order
for(int i=0;i<numberOfPainters;i++){
for(int j=0;j<numberOfFences;j++)
dp[i][j] = Long.MAX_VALUE;
}
// Filling the values for first painter
for(int i=0;i<numberOfFences;i++)dp[0][i] = pref[i];
// Now solving for painters 2, 3, 4......n
for(int i=1;i<numberOfPainters;i++){
for(int j=i;j<numberOfFences;j++){
for(int k=i;k<=j;k++){
long timeTakenForithPainter = pref[j] - pref[k-1];
dp[i][j] = Math.min(dp[i][j], Math.max(dp[i-1][k-1], timeTakenForithPainter));
}
}
}
if(numberOfPainters > numberOfFences)return dp[numberOfFences-1][numberOfFences-1];
return dp[numberOfPainters-1][numberOfFences-1];
}
public static void main (String[] args) throws IOException {
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while(t-- > 0){
int numberOfPainters = sc.nextInt();
long timePerUnit = sc.nextLong();
int numberOfFences = sc.nextInt();
long fenceSize[] = new long[numberOfFences];
for(int i=0;i<numberOfFences;i++) fenceSize[i] = sc.nextLong();
long ans = solvePaintersPartitionProblem(numberOfPainters, timePerUnit, numberOfFences, fenceSize);
System.out.println(ans);
}
}
}
2 2 5 2// number of painters, time taken paint a unit length of fence and number of fences 1 10 // fences size 10 1 4 1 8 11 3
50 11
복잡성 분석
시간 복잡성: O (N * M ^ 2)
여기서 N = 화가 수
M = 울타리의 수, 여기서는 i 번째 화가가 보낸 시간을 찾기 위해 접두사 합계를 사용하므로 시간 복잡성을 줄였습니다.
첫 번째 루프는 여러 화가에 걸쳐 실행되고 중첩 된 루프는 펜스 수에 걸쳐 실행됩니다. N = M이면 시간 복잡도 : 화가의 파티션 문제에 대한 O (N ^ 3).
공간 복잡성: O (N * M)
N = 화가 수
M = 울타리 수, N * M 차원의 2D DP 배열이 있기 때문입니다. 따라서 우리는 화가의 분할 문제에 대한 다항식 공간 복잡성 솔루션을 가지고 있습니다.
