Minimice el costo de atravesar los arreglos con el costo de cambio de arreglo dado

Posted on by Rudeus Greyrat

Dados tres arreglos A[] , B[] y C[] de tamaño N cada uno y dos enteros X e Y , la tarea es encontrar el costo mínimo para llegar al final de los arreglos con las siguientes condiciones:

  • Seleccione uno de los tres elementos en cada índice. 
  • Para cambiar de la primera array a la segunda o viceversa, se requieren puntos  X adicionales y
  • Para cambiar de la segunda array a la tercera o viceversa, se requieren puntos Y adicionales.
  • El primer elemento (en el índice 0) debe seleccionarse solo de la primera array.

Nota: No es posible cambiar directamente del primer al tercer arreglo o viceversa.

Ejemplos:

Entrada:  X = 6, Y = 3
A[] = { 30, 10, 40, 2, 30, 30 }
B[] = { 10, -5, 10, 50, 7, 18 }
C[] = { 4 , 20, 7, 23, 2, 10 }
Salida: 75
Explicación: Seleccionamos estos elementos en el índice (0 a N-1). 
A[] = { 30, 10, 40, 2 , 30, 30 }
B[] = { 10, -5 , 10 , 50, 7 , 18 }
C[] = { 4, 20, 7, 23, 2, 10 }
Del índice 0 tenemos que seleccionar 30. Entonces, el costo total para recorrer hasta el índice 0 es 30.
Ahora, en el índice 1, 3 opciones (10, -5, 20). Así que seleccione -5 de la segunda array.
Entonces, se requiere un costo adicional de X (X = 6) para cambiar de la primera array a la segunda. 
Entonces, el costo total para recorrer hasta el índice 1 es 30 + 6 – 5 = 31.
En el índice 2, seleccione 10. Entonces, el costo total para recorrer hasta el índice 2 es 31+10= 41.
En el índice 3, seleccione 2 de la primera array,  
Entonces, se requieren X (X = 6) puntos adicionales para cambiar de la segunda array a la primera. 
Entonces, el costo total para recorrer hasta el índice 3 es 41+6+2 = 49 y así sucesivamente.
Entonces, costo total = 30 + ( 6 +(-5)) + 10 + ( 6 +2) + ( 6 +7) + ( 3 +10) = 75
6 y 3 son los costos adicionales necesarios para cambiar la array.

Entrada:  X = -5, Y = 4
A[] = { 30, 10, -15, 10, 50, 7 }
B[] = { 4, 20, 7, 23, 2, 18 }
C[] = { 30, 10, 40, 2, 30, 10 }
Salida: 34

 

Enfoque: El problema se puede resolver con base en el Enfoque Greedy basado en la siguiente idea:

En cada índice, intente incluir el elemento de la array que incluirá el costo mínimo. Y también tenga en cuenta que podemos ir de A[] a B[] , B[] a C[] , B[] a A[] y C[] a B[] no de A[] a C[] o C[] a A[] . 

Siga los siguientes pasos para implementar la idea:

  • Cree una array 2D (digamos min_pnts [N][3]).
  • Recorra la array desde el último índice hasta el primer índice y en cada iteración:
    • El valor de min_pnts[i][0] depende de min_pnts[i+1][0] y min_pnts[i+1][1] , el valor de min_pnts[i][1] depende de min_pnts[i+1][ 1], min_pnts[i+1][0] y min_pnts[i+1][2] , el valor de min_pnts[i][2] depende de min_pnts[i+1][2] y min_pnts[i+1] [1] .
    • Verifique qué ruta requiere puntos mínimos (es decir, con array de conmutación o no).
    • Almacene los puntos mínimos requeridos si seleccionamos el elemento de índice actual de la array 1, 2 o 3.
  • Devuelve los puntos mínimos necesarios para atravesar la array.

A continuación se muestra la implementación del enfoque anterior.

C++

// C++ code to implement above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find minimum cost
// to traverse till the end point
int solve(vector<int> A, vector<int> B,
          vector<int> C, int N, int X, int Y)
{
    // Initialize one 2D vector
    vector<vector<int> > min_pnts(3, vector<int>(N, 0));
    min_pnts[0][N - 1] = A[N - 1];
    min_pnts[1][N - 1] = B[N - 1];
    min_pnts[2][N - 1] = C[N - 1];
 
    // Start traversing the array
    // by using minimum points
    for (int i = N - 2; i >= 0; i--) {
        min_pnts[0][i]
            = A[i] + min(min_pnts[0][i + 1],
                         min_pnts[1][i + 1]
                             + X);
        min_pnts[1][i]
            = B[i] + min({ min_pnts[0][i + 1] + X,
                           min_pnts[1][i + 1],
                           min_pnts[2][i + 1] + Y });
        min_pnts[2][i]
            = C[i] + min(min_pnts[2][i + 1],
                         min_pnts[1][i + 1]
                             + Y);
    }
 
    return min_pnts[0][0];
}
 
// Driver code
int main()
{
    int X = 6, Y = 3;
    vector<int> A = { 30, 10, 40, 2, 30, 30 };
    vector<int> B = { 10, -5, 10, 50, 7, 18 };
    vector<int> C = { 4, 20, 7, 23, 2, 10 };
 
    // Function call
    cout << solve(A, B, C, A.size(), X, Y);
    return 0;
}

Java

// Java code to implement above approach
import java.io.*;
 
class GFG
{
 
  // Function to find minimum cost
  // to traverse till the end point
  public static int solve(int A[], int B[], int C[],
                          int N, int X, int Y)
  {
 
    // Initialize one 2D vector
    int min_pnts[][] = new int[3][N];
    min_pnts[0][N - 1] = A[N - 1];
    min_pnts[1][N - 1] = B[N - 1];
    min_pnts[2][N - 1] = C[N - 1];
 
    // Start traversing the array
    // by using minimum points
    for (int i = N - 2; i >= 0; i--) {
      min_pnts[0][i]
        = A[i]
        + Math.min(min_pnts[0][i + 1],
                   min_pnts[1][i + 1] + X);
      min_pnts[1][i]
        = B[i]
        + Math.min(
        min_pnts[0][i + 1] + X,
        Math.min(min_pnts[1][i + 1],
                 min_pnts[2][i + 1] + Y));
      min_pnts[2][i]
        = C[i]
        + Math.min(min_pnts[2][i + 1],
                   min_pnts[1][i + 1] + Y);
    }
 
    return min_pnts[0][0];
  }
 
  // Driver Code
  public static void main(String[] args)
  {
    int X = 6, Y = 3;
    int A[] = { 30, 10, 40, 2, 30, 30 };
    int B[] = { 10, -5, 10, 50, 7, 18 };
    int C[] = { 4, 20, 7, 23, 2, 10 };
 
    // Function call
    System.out.print(solve(A, B, C, A.length, X, Y));
  }
}
 
// This code is contributed by Rohit Pradhan

Python3

# python3 code to implement above approach
 
# Function to find minimum cost
# to traverse till the end point
def solve(A, B, C, N, X, Y):
 
    # Initialize one 2D vector
    min_pnts = [[0 for _ in range(N)] for _ in range(3)]
    min_pnts[0][N - 1] = A[N - 1]
    min_pnts[1][N - 1] = B[N - 1]
    min_pnts[2][N - 1] = C[N - 1]
 
    # Start traversing the array
    # by using minimum points
    for i in range(N-2, -1, -1):
        min_pnts[0][i] = A[i] + min(min_pnts[0][i + 1],
                                    min_pnts[1][i + 1]
                                    + X)
        min_pnts[1][i] = B[i] + min({min_pnts[0][i + 1] + X,
                                     min_pnts[1][i + 1],
                                     min_pnts[2][i + 1] + Y})
        min_pnts[2][i] = C[i] + min(min_pnts[2][i + 1],
                                    min_pnts[1][i + 1]
                                    + Y)
 
    return min_pnts[0][0]
 
# Driver code
if __name__ == "__main__":
 
    X, Y = 6, 3
    A = [30, 10, 40, 2, 30, 30]
    B = [10, -5, 10, 50, 7, 18]
    C = [4, 20, 7, 23, 2, 10]
 
    # Function call
    print(solve(A, B, C, len(A), X, Y))
 
    # This code is contributed by rakeshsahni

C#

// C# code to implement above approach
using System;
 
class GFG {
 
  // Function to find minimum cost
  // to traverse till the end point
  static int solve(int[] A, int[] B, int[] C, int N,
                   int X, int Y)
  {
 
    // Initialize one 2D vector
    int[, ] min_pnts = new int[3, N];
    min_pnts[0, N - 1] = A[N - 1];
    min_pnts[1, N - 1] = B[N - 1];
    min_pnts[2, N - 1] = C[N - 1];
 
    // Start traversing the array
    // by using minimum points
    for (int i = N - 2; i >= 0; i--) {
      min_pnts[0, i]
        = A[i]
        + Math.Min(min_pnts[0, i + 1],
                   min_pnts[1, i + 1] + X);
      min_pnts[1, i]
        = B[i]
        + Math.Min(
        min_pnts[0, i + 1] + X,
        Math.Min(min_pnts[1, i + 1],
                 min_pnts[2, i + 1] + Y));
      min_pnts[2, i]
        = C[i]
        + Math.Min(min_pnts[2, i + 1],
                   min_pnts[1, i + 1] + Y);
    }
 
    return min_pnts[0, 0];
  }
 
  // Driver Code
  public static void Main()
  {
    int X = 6, Y = 3;
    int[] A = { 30, 10, 40, 2, 30, 30 };
    int[] B = { 10, -5, 10, 50, 7, 18 };
    int[] C = { 4, 20, 7, 23, 2, 10 };
 
    // Function call
    Console.Write(solve(A, B, C, A.Length, X, Y));
  }
}
 
// This code is contributed by Samim Hossain Mondal.

Javascript

<script>
    // JavaScript code for the above approach
 
  // Function to find minimum cost
  // to traverse till the end point
  function solve(A, B, C, N, X, Y)
  {
 
    // Initialize one 2D vector
        var min_pnts = new Array(3);
   
    // Loop to create 2D array using 1D array
    for (var i = 0; i < N; i++) {
        min_pnts[i] = new Array(3);
    }
     
    min_pnts[0][N - 1] = A[N - 1];
    min_pnts[1][N - 1] = B[N - 1];
    min_pnts[2][N - 1] = C[N - 1];
 
    // Start traversing the array
    // by using minimum point
    for (let i = N - 2; i >= 0; i--) {
      min_pnts[0][i]
        = A[i]
        + Math.min(min_pnts[0][i + 1],
                   min_pnts[1][i + 1] + X);
      min_pnts[1][i]
        = B[i]
        + Math.min(
        min_pnts[0][i + 1] + X,
        Math.min(min_pnts[1][i + 1],
                 min_pnts[2][i + 1] + Y));
      min_pnts[2][i]
        = C[i]
        + Math.min(min_pnts[2][i + 1],
                   min_pnts[1][i + 1] + Y);
    }
 
    return min_pnts[0][0];
  }
 
    // Driver Code
 
    let X = 6, Y = 3;
    let A = [ 30, 10, 40, 2, 30, 30 ];
    let B = [ 10, -5, 10, 50, 7, 18 ];
    let C = [ 4, 20, 7, 23, 2, 10 ];
 
    // Function call
    document.write(solve(A, B, C, A.length, X, Y));
 
// This code is contributed by sanoy_62.
</script>
Producción

75

Tiempo Complejidad: O(N)
Espacio auxiliar: O(N)

Publicación traducida automáticamente

Artículo escrito por khatriharsh281 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *