Dada uma placa de dimensões n × m que precisa ser cortado em quadrados n × m. O custo de fazer um corte ao longo de uma borda horizontal ou vertical é fornecido em duas matrizes:

• x[] : Corte de custos ao longo das bordas verticais (longitudinalmente).
• e[] : Corte de custos ao longo das bordas horizontais (em largura).

Encontre o custo total mínimo necessário para cortar o tabuleiro em quadrados de maneira ideal.

Exemplos: 

Entrada: x[] = [2 1 3 1 4] y[] = [4 1 2] n = 4 m = 6
Saída: 42
Explicação:

Inicialmente não. de segmentos horizontais = 1 e não. de segmentos verticais = 1.
A maneira ideal de cortar em quadrado é:
Escolha 4 (de x) -> corte vertical Custo = 4 × segmentos horizontais = 4
 Agora segmentos horizontais = 1 segmentos verticais = 2.
Escolha 4 (de y) -> corte horizontal Custo = 4 × segmentos verticais = 8
 Agora segmentos horizontais = 2 segmentos verticais = 2.
Escolha 3 (de x) -> corte vertical Custo = 3 × segmentos horizontais = 6
 Agora segmentos horizontais = 2 segmentos verticais = 3.
Escolha 2 (de x) -> corte vertical Custo = 2 × segmentos horizontais = 4
 Agora segmentos horizontais = 2 segmentos verticais = 4.
Escolha 2 (de y) -> corte horizontal Custo = 2 × segmentos verticais = 8
 Agora segmentos horizontais = 3 segmentos verticais = 4.
Escolha 1 (de x) -> corte vertical Custo = 1 × segmentos horizontais = 3
Agora segmentos horizontais = 3 segmentos verticais = 5.
Escolha 1 (de x) -> corte vertical Custo = 1 × segmentos horizontais = 3
Agora segmentos horizontais = 3 segmentos verticais = 6.
Escolha 1 (de y) -> corte horizontal Custo = 1 × segmentos verticais = 6
Agora segmentos horizontais = 4 segmentos verticais = 6.
Portanto, o custo total = 4 + 8 + 6 + 4 + 8 + 3 + 3 + 6 = 42.

Entrada: x[] = [1 1 1] y[] = [1 1 1] n = 4 m = 4
Saída: 15
Explicação:
Inicialmente não. de segmentos horizontais = 1 e não. de segmentos verticais = 1.
A maneira ideal de cortar em quadrado é:
Escolha 1 (de y) -> corte horizontal Custo = 1 × segmentos verticais = 1
Agora segmentos horizontais = 2 segmentos verticais = 1.
Escolha 1 (de y) -> corte horizontal Custo = 1 × segmentos verticais = 1
Agora segmentos horizontais = 3 segmentos verticais = 1.
Escolha 1 (de y) -> corte horizontal Custo = 1 × segmentos verticais = 1
Agora segmentos horizontais = 4 segmentos verticais = 1.
Escolha 1 (de x) -> corte vertical Custo = 1 × segmentos horizontais = 4
Agora segmentos horizontais = 4 segmentos verticais = 2.
Escolha 1 (de x) -> corte vertical Custo = 1 × segmentos horizontais = 4
Agora segmentos horizontais = 4 segmentos verticais = 3.
Escolha 1 (de x) -> corte vertical Custo = 1 × segmentos horizontais = 4
Agora segmentos horizontais = 4 segmentos verticais = 4
Portanto, o custo total = 1 + 1 + 1 + 4 + 4 + 4 = 15.

Índice

• [Abordagem ingênua] Experimente todas as permutações - O((n+m)!×(n+m)) Tempo e O(n+m) Espaço
• [Abordagem esperada] Usando técnica gananciosa - O( n (log n)+m (log m)) Tempo e O(1) Espaço

[Abordagem ingênua] Experimente todas as permutações - O((n+m)!×(n+m)) Tempo e O(n+m) Espaço

A ideia é gerar todas as permutações possíveis dos cortes fornecidos e depois calcular o custo de cada permutação. Por fim, retorne o custo mínimo entre eles.

Observação: Esta abordagem não é viável para entradas maiores porque o número de permutações cresce fatorialmente como (m+n-2)!.
Para cada permutação devemos calcular o custo em tempo O(m+n). Conseqüentemente, a complexidade geral do tempo torna-se O((m+n−2)!×(m+n)).

[Abordagem esperada] Usando técnica gananciosa - O( n (log n)+m (log m)) Tempo e O(1) Espaço

A ideia é fazer primeiro os cortes mais caros usando um abordagem gananciosa . A observação é que escolher o maior corte de custos em cada etapa reduz os custos futuros ao afetar várias peças ao mesmo tempo. Classificamos os custos de corte vertical (x) e horizontal (y) em ordem decrescente e, em seguida, escolhemos iterativamente o maior para maximizar a economia de custos. Os cortes restantes são processados ​​separadamente para garantir que todas as seções sejam divididas de maneira ideal.

O que acontece quando fazemos um corte?

• Corte horizontal → você está cortando na largura para que o número de faixas horizontais aumente (hCount++). Mas o custo é multiplicado por vCount (o número de tiras verticais) porque o corte horizontal tem que passar por todos os segmentos verticais.
• Corte vertical → você está cortando na altura para que o número de faixas verticais aumente (vCount++). Mas o custo é multiplicado por hCount (o número de faixas horizontais) porque o corte vertical tem que passar por todos os segmentos horizontais.

Passos para resolver o problema:

• Classifique as matrizes x e y em ordem decrescente.
• Use dois ponteiros, um para x e outro para y, começando do valor maior e avançando em direção a valores menores.
• Mantenha hCount e vCount para rastrear quantos segmentos cada corte afeta e atualizá-los adequadamente.
• Itere enquanto x e y têm cortes não processados, sempre escolhendo o custo maior para minimizar as despesas gerais.
• Se x tiver cortes restantes, processe-os com o multiplicador hCount; da mesma forma, processe os cortes restantes com vCount.
• Acumule o custo total em cada etapa usando a fórmula: corte de custo * número de peças afetadas garantindo custo mínimo.

#include   #include #include   using namespace std; int minCost(int n int m   vector<int>& x vector<int>& y) {    // Sort the cutting costs in ascending order  sort(x.begin() x.end());  sort(y.begin() y.end());   int hCount = 1 vCount = 1;   int i = x.size() - 1 j = y.size() - 1;   int totalCost = 0;  while (i >= 0 && j >= 0) {    // Choose the larger cost cut to   // minimize future costs  if (x[i] >= y[j]) {  totalCost += x[i] * hCount;   vCount++;  i--;  }   else {  totalCost += y[j] * vCount;   hCount++;  j--;  }  }  // Process remaining vertical cuts  while (i >= 0) {  totalCost += x[i] * hCount;  vCount++;  i--;  }  // Process remaining horizontal cuts  while (j >= 0) {  totalCost += y[j] * vCount;  hCount++;  j--;  }  return totalCost; } int main() {    int n = 4 m = 6;  vector<int> x = {2 1 3 1 4};  vector<int> y = {4 1 2};  cout << minCost(n m x y) << endl;  return 0; } 

import java.util.Arrays; class GfG {    static int minCost(int n int m   int[] x int[] y) {    // Sort the cutting costs in ascending order  Arrays.sort(x);  Arrays.sort(y);   int hCount = 1 vCount = 1;   int i = x.length - 1 j = y.length - 1;   int totalCost = 0;  while (i >= 0 && j >= 0) {    // Choose the larger cost cut to   // minimize future costs  if (x[i] >= y[j]) {  totalCost += x[i] * hCount;   vCount++;  i--;  }   else {  totalCost += y[j] * vCount;   hCount++;  j--;  }  }  // Process remaining vertical cuts  while (i >= 0) {  totalCost += x[i] * hCount;  vCount++;  i--;  }  // Process remaining horizontal cuts  while (j >= 0) {  totalCost += y[j] * vCount;  hCount++;  j--;  }  return totalCost;  }  public static void main(String[] args) {    int n = 4m = 6;  int[] x = {2 1 3 1 4};  int[] y = {4 1 2};  System.out.println(minCost(n m x y));  } } 

def minCost(nm x y): # Sort the cutting costs in ascending order x.sort() y.sort() hCount vCount = 1 1 i j = len(x) - 1 len(y) - 1 totalCost = 0 while i >= 0 and j >= 0: # Choose the larger cost cut to  # minimize future costs if x[i] >= y[j]: totalCost += x[i] * hCount vCount += 1 i -= 1 else: totalCost += y[j] * vCount hCount += 1 j -= 1 # Process remaining vertical cuts while i >= 0: totalCost += x[i] * hCount vCount += 1 i -= 1 # Process remaining horizontal cuts while j >= 0: totalCost += y[j] * vCount hCount += 1 j -= 1 return totalCost if __name__ == '__main__': nm = 4 6 x = [2 1 3 1 4] y = [4 1 2] print(minCost(nmx y)) 

using System; class GfG {  public static int minCost(int n int m   int[] x int[] y) {    // Sort the cutting costs in ascending order  Array.Sort(x);  Array.Sort(y);  int hCount = 1 vCount = 1;  int i = x.Length - 1 j = y.Length - 1;  int totalCost = 0;  // Process the cuts in greedy manner  while (i >= 0 && j >= 0) {    // Choose the larger cost cut to   // minimize future costs  if (x[i] >= y[j]) {  totalCost += x[i] * hCount;  vCount++;  i--;  }  else {  totalCost += y[j] * vCount;  hCount++;  j--;  }  }  // Process remaining vertical cuts  while (i >= 0) {  totalCost += x[i] * hCount;  vCount++;  i--;  }  // Process remaining horizontal cuts  while (j >= 0) {  totalCost += y[j] * vCount;  hCount++;  j--;  }  return totalCost;  }    public static void Main() {    int n=4m=6;  int[] x = {2 1 3 1 4};  int[] y = {4 1 2};  Console.WriteLine(minCost(nm x y));  } } 

function minCost( nm x y) {    // Sort the cutting costs in ascending order  x.sort((a b) => a - b);  y.sort((a b) => a - b);  let hCount = 1 vCount = 1;  let i = x.length - 1 j = y.length - 1;  let totalCost = 0;  while (i >= 0 && j >= 0) {    // Choose the larger cost cut to   // minimize future costs  if (x[i] >= y[j]) {  totalCost += x[i] * hCount;  vCount++;  i--;  }   else {  totalCost += y[j] * vCount;  hCount++;  j--;  }  }  // Process remaining vertical cuts  while (i >= 0) {  totalCost += x[i] * hCount;  vCount++;  i--;  }  // Process remaining horizontal cuts  while (j >= 0) {  totalCost += y[j] * vCount;  hCount++;  j--;  }  return totalCost; } // Driver Code let n = 4m = 6; let x = [2 1 3 1 4]; let y = [4 1 2]; console.log(minCost(nm x y)); 

42