Праблема раздзела мастака


Узровень складанасці Жорсткі
Часта пытаюцца ў CodeNation Google
Двайковы пошук Падзялі і перамагай Дынамічнае праграмаванне Пошук

Пастаноўка праблемы

Праблема раздзелу мастака сцвярджае, што ў нас ёсць некаторыя агароджы і ёсць некаторыя мастакі. Мы хочам мінімізаваць час афарбоўкі ўсіх платоў мастакамі. Ёсць парадак афарбоўкі платоў мастакамі. Улічыце, што ў нас ёсць п маляры, тады маляр з індэксам "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, ... п. Для рашэння задачы для 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

Код 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 = колькасць платоў, паколькі мы выкарыстоўваем тут прыстаўную суму для знаходжання часу, праведзенага i-м маляром, мы паменшылі складанасць часу.

Першая пятля праходзіць па колькасці маляроў, а ўкладзеныя завесы - па колькасці платоў. Калі N = M, складанасць часу: O (N ^ 3) для праблемы раздзелу мастака.

Касмічная складанасць: O (N * M)

Дзе N = колькасць мастакоў 

M = колькасць платоў, таму што ў нас масіў 2D DP памераў N * M. Такім чынам, мы маем рашэнне складанасці шматчленнай прасторы для праблемы раздзелу мастака.