דער מאָלער צעטיילונג פּראָבלעם


שוועריקייט לעוועל שווער
אָפט געבעטן אין קאָדנאַטיאָן גוגל
ביינערי זוכן צעטיילן און קאַנגקער דינאַמיש פּראָגראַממינג שאַרף

פּראָבלעם סטאַטעמענט

די פּראָבלעם פון די מאָלער ס צעטיילונג שטאַטן אַז מיר האָבן עטלעכע פענסעס און מיר האָבן עטלעכע פּיינערז. מיר וועלן צו מינאַמייז די צייט פון פּיינינגז אַלע די פענסעס דורך פּיינערז. דער סדר איז פּיינטיד דורך פּיינטינגז די פענסעס דורך פּיינערז. באַטראַכטן אַז מיר האָבן N פּיינערז, דער מאָלער מיט אינדעקס 'איך' קענען פּיינט פענסעס בלויז אין קעסיידערדיק סדר.

אַזוי, דער מיטל דער ערשטער מאָלער וועט מאָלן עטלעכע פון ​​די פענסעס. דערנאָך די רגע מאָלער פּיינט עטלעכע פון ​​די פענסעס. דער זעלביקער גייט פֿאַר אַלע פּיינערז. דאָס קען פּאַסירן אַז עטלעכע קינסטלער קען נישט אפילו באַקומען אַ פּלויט צו מאָלן.

בייַשפּיל

דער מאָלער צעטיילונג פּראָבלעם

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.

צוגאַנג צו דער צעטיילונג פון דער מאָלער

מיר וועלן נוצן דינאַמיש פּראָגראַממינג פֿאַר סאַלווינג דעם פּראָבלעם. דאָ, מיר וועלן אויך נוצן אַ זייער גוט דיפיינד דינאַמיש פּראָגראַממינג טעכניק (פּרעפיקס סומע) פֿאַר גענומען די סומע פון ​​צייט אין אָ (1) צייט קאַמפּלעקסיטי. ערשטער, מיר וועלן סאָלווע די פּראָבלעם פֿאַר איין מאָלער. דערנאָך מיר סאָלווע די נומער פון פּיינערז אויף די דנאָ-אַרויף = 2, 3, 4, ... n. צו לייזן דעם פּראָבלעם פֿאַר אַ יטה מאָלער, מיר וועלן געפֿינען די צייט פון יטה מאָלער צו מאָלן פּלויט ק צו דזש. דאָ, מיר האָבן באטראכט אַז דער מאָלער וועט פּיינט פּלויט ק צו דזש און פענסעס פון 1 צו (ק -1) איז פּיינטיד דורך (איך -1) פּיינערז. דער ענטפער פֿאַר דעם סאַב-פּראָבלעם זאָל זיין די מאַקסימום צייט פון (i-1) פּיינערז אָדער יטה מאָלער. אין דעם שטייגער, מיר האַלטן סאַלווינג קלענערער סאַב-פּראָבלעמס. דערנאָך, קאַמביינינג די רעזולטאַט פון די סמאָלער סאַב-פּראָבלעמס, מיר סאָלווע אונדזער ערשט פּראָבלעם (דער צעטיילונג פון דער מאָלער).

קאָדעקס

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

Java קאוד פֿאַר מאָלער ס צעטיילונג פּראָבלעם

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 = נומער פון פענסעס, ווייַל מיר נוצן די פּרעפיקס סומע צו געפֿינען די צייט פארבראכט דורך די מאָלער, מיר האָבן רידוסט די קאַמפּלעקסיטי פון צייט.

דער ערשטער שלייף לויפט איבער נומער פון פּיינערז, און נעסטעד לופּס לויפן איבער די נומער פון פענסעס. אויב N = M, צייט קאַמפּלעקסיטי: O (N ^ 3) פֿאַר די צעטיילונג פון דער מאָלער.

ספעיס קאַמפּלעקסיטי: O (N * M)

וווּ N = נומער פון פּיינערז 

M = נומער פון פענסעס ווייַל מיר האָבן אַ 2 ד דפּ מענגע פון ​​דימענשאַנז N * M. אַזוי מיר האָבן אַ פּאָלינאָמיאַל אָרט קאַמפּלעקסיטי לייזונג פֿאַר דער צעטיילונג פּראָבלעם פון דער מאָלער.