Проблема перегородки художника


Сложный уровень Жесткий
Часто спрашивают в CodeNation Google
Бинарный поиск Разделяй и властвуй Динамическое программирование Поиск

Постановка задачи

Задача 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

Код 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. Таким образом, у нас есть полиномиальное пространственное решение для задачи художника о разбиении.