Dota izmēru dēlis n × m kas jāsagriež n × m kvadrātos. Izmaksas par griezumu gar horizontālu vai vertikālu malu ir norādītas divos masīvos:

• x[] : Griešanas izmaksas gar vertikālajām malām (garuma virzienā).
• un [] : Griešanas izmaksas pa horizontālajām malām (platuma virzienā).

Atrodiet minimālās kopējās izmaksas, kas nepieciešamas, lai dēli optimāli sagrieztu kvadrātos.

Piemēri: 

Ievade: x[] = [2 1 3 1 4] y[] = [4 1 2] n = 4 m = 6
Izvade: 42
Paskaidrojums:

Sākotnēji nē. horizontālo segmentu = 1 un nē. vertikālo segmentu skaits = 1.
Optimālais veids, kā sagriezt kvadrātā, ir:
Izvēlieties 4 (no x) -> vertikālais griezums Izmaksas = 4 × horizontālie segmenti = 4
 Tagad horizontālie segmenti = 1 vertikālie segmenti = 2.
Izvēlieties 4 (no y) -> horizontāls griezums Izmaksas = 4 × vertikālie segmenti = 8
 Tagad horizontālie segmenti = 2 vertikālie segmenti = 2.
Izvēlieties 3 (no x) -> vertikālais griezums Izmaksas = 3 × horizontālie segmenti = 6
 Tagad horizontālie segmenti = 2 vertikālie segmenti = 3.
Izvēlieties 2 (no x) -> vertikālais griezums Izmaksas = 2 × horizontālie segmenti = 4
 Tagad horizontālie segmenti = 2 vertikālie segmenti = 4.
Izvēlieties 2 (no y) -> horizontāls griezums Izmaksas = 2 × vertikālie segmenti = 8
 Tagad horizontālie segmenti = 3 vertikālie segmenti = 4.
Izvēlieties 1 (no x) -> vertikālais griezums Izmaksas = 1 × horizontālie segmenti = 3
Tagad horizontālie segmenti = 3 vertikālie segmenti = 5.
Izvēlieties 1 (no x) -> vertikālais griezums Izmaksas = 1 × horizontālie segmenti = 3
Tagad horizontālie segmenti = 3 vertikālie segmenti = 6.
Izvēlieties 1 (no y) -> horizontāls griezums Izmaksas = 1 × vertikālie segmenti = 6
Tagad horizontālie segmenti = 4 vertikālie segmenti = 6.
Tātad kopējās izmaksas = 4 + 8 + 6 + 4 + 8 + 3 + 3 + 6 = 42.

Ievade: x[] = [1 1 1] y[] = [1 1 1] n = 4 m = 4
Izvade: 15
Paskaidrojums:
Sākotnēji nē. horizontālo segmentu = 1 un nē. vertikālo segmentu skaits = 1.
Optimālais veids, kā sagriezt kvadrātā, ir:
Izvēlieties 1 (no y) -> horizontāls griezums Izmaksas = 1 × vertikālie segmenti = 1
Tagad horizontālie segmenti = 2 vertikālie segmenti = 1.
Izvēlieties 1 (no y) -> horizontāls griezums Izmaksas = 1 × vertikālie segmenti = 1
Tagad horizontālie segmenti = 3 vertikālie segmenti = 1.
Izvēlieties 1 (no y) -> horizontāls griezums Izmaksas = 1 × vertikālie segmenti = 1
Tagad horizontālie segmenti = 4 vertikālie segmenti = 1.
Izvēlieties 1 (no x) -> vertikālais griezums Izmaksas = 1 × horizontālie segmenti = 4
Tagad horizontālie segmenti = 4 vertikālie segmenti = 2.
Izvēlieties 1 (no x) -> vertikālais griezums Izmaksas = 1 × horizontālie segmenti = 4
Tagad horizontālie segmenti = 4 vertikālie segmenti = 3.
Izvēlieties 1 (no x) -> vertikālais griezums Izmaksas = 1 × horizontālie segmenti = 4
Tagad horizontālie segmenti = 4 vertikālie segmenti = 4
Tātad kopējās izmaksas = 1 + 1 + 1 + 4 + 4 + 4 = 15.

Satura rādītājs

• [Naīvā pieeja] Izmēģiniet visas permutācijas — O((n+m)!×(n+m)) laiks un O(n+m) telpa
• [Paredzamā pieeja], izmantojot mantkārīgo paņēmienu — O(n (log n)+m (log m)) laiks un O(1) telpa

[Naīvā pieeja] Izmēģiniet visas permutācijas — O((n+m)!×(n+m)) laiks un O(n+m) telpa

Ideja ir ģenerēt visas iespējamās doto griezumu permutācijas un pēc tam aprēķināt katras permutācijas izmaksas. Visbeidzot atdodiet minimālās izmaksas starp tām.

Piezīme: Šī pieeja nav iespējama lielākiem ievadiem, jo ​​permutāciju skaits pieaug faktoriāli kā (m+n-2)!.
Katrai permutācijai mums jāaprēķina izmaksas O(m+n) laikā. Tādējādi kopējā laika sarežģītība kļūst par O((m+n−2)!×(m+n)).

[Paredzamā pieeja], izmantojot mantkārīgo paņēmienu — O(n (log n)+m (log m)) laiks un O(1) telpa

Ideja ir vispirms veikt visdārgākos samazinājumus, izmantojot a mantkārīga pieeja . Novērojums ir tāds, ka, izvēloties visaugstāko izmaksu samazinājumu katrā posmā, tiek samazinātas turpmākās izmaksas, vienlaikus ietekmējot vairākus gabalus. Mēs sakārtojam vertikālo (x) un horizontālo (y) izmaksu samazināšanu dilstošā secībā, pēc tam iteratīvi izvēlamies lielāko, lai palielinātu izmaksu ietaupījumu. Atlikušie griezumi tiek apstrādāti atsevišķi, lai nodrošinātu visu sekcijas optimālu sadalīšanu.

Kas notiek, kad veicam griezumu?

• Horizontāls griezums → jūs griežat visā platumā, tādējādi palielināsies horizontālo joslu skaits (hCount++). Bet izmaksas tiek reizinātas ar vCount (vertikālo joslu skaitu), jo horizontālajam griezumam ir jāiziet cauri visiem vertikālajiem segmentiem.
• Vertikāls griezums → jūs griežat visā augstumā, tāpēc palielinās vertikālo joslu skaits (vCount++). Bet izmaksas tiek reizinātas ar hCount (horizontālo joslu skaitu), jo vertikālajam griezumam ir jāiziet cauri visiem horizontālajiem segmentiem.

Problēmas risināšanas soļi:

• Kārtojiet gan x un y masīvus dilstošā secībā.
• Izmantojiet divus rādītājus vienu x un otru y — sākot no lielākās vērtības un virzoties uz mazākām vērtībām.
• Uzturiet hCount un vCount, lai izsekotu, cik segmentu katrs griezums ietekmē, un attiecīgi atjauninātu tos.
• Atkārtojiet, kamēr gan x , gan y ir neapstrādāti samazinājumi, vienmēr izvēloties lielākās izmaksas, lai samazinātu kopējos izdevumus.
• Ja x ir atlikuši samazinājumi, apstrādājiet tos ar hCount reizinātāju; līdzīgi apstrādājiet atlikušos y izgriezumus, izmantojot vCount.
• Uzkrāt kopējās izmaksas katrā darbībā, izmantojot formulu: samazināt izmaksas * ietekmēto gabalu skaits, nodrošinot minimālas izmaksas.

#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