Dados dos arreglos A[] y B[] de N enteros positivos y un costo C . Podemos elegir cualquier elemento de cada índice de las arrays dadas, es decir, para cualquier índice i podemos elegir solo el elemento A[i] o B[i] . La tarea es encontrar la suma total mínima de seleccionar N elementos de las dos arrays dadas y si estamos seleccionando cualquier elemento de A[] a B[] o viceversa en la siguiente iteración, entonces el costo C también se suma al suma.
Nota: Elija el elemento en orden creciente de índice, es decir, 0 ≤ i < N .
Ejemplos:
Entrada: N = 9, A[] = {7, 6, 18, 6, 16, 18, 1, 17, 17}, B[] = {6, 9, 3, 10, 9, 1, 10, 1 , 5}, C = 2
Salida: 49
Explicación:
Al tomar el primer elemento del arreglo A, suma = 7
Al tomar el segundo elemento del arreglo A, suma = 7 + 6 = 13
Al tomar el tercer elemento del arreglo B, como estamos ingresando de la array A a la array B, suma = 13 + 3 + 2 = 18
Al tomar el cuarto elemento de la array A, como estamos ingresando de la array B a la array A, suma = 18 + 6 + 2 = 26
Al tomar el 5to elemento del arreglo B, como estamos ingresando del arreglo A al arreglo B, suma = 26 + 9 + 2 = 37
Al tomar el 6to elemento del arreglo B, suma = 37 + 1 = 38
Al tomar el séptimo elemento del arreglo A, mientras ingresamos del arreglo B al arreglo A, suma = 38 + 1 + 2 = 41
Al tomar el octavo elemento del arreglo B, mientras ingresamos del arreglo A al arreglo B, suma = 41 + 1 + 2 = 44
Al tomar el noveno elemento de la array B, suma = 44 + 5 = 49.Entrada: N = 9, A = {3, 2, 3, 1, 3, 3, 1, 4, 1}, B = {1, 2, 3, 4, 4, 1, 2, 1, 3}, C = 1
Salida: 18
Explicación:
Al tomar el primer elemento del arreglo B, suma = 1
Al tomar el segundo elemento del arreglo A, suma = 1 + 2 = 3
Al tomar el tercer elemento del arreglo A, suma = 3 + 3 = 6
Al tomar el 4to elemento del arreglo A, suma = 6 + 1 = 7
Al tomar el 5to elemento del arreglo A, suma = 7 + 3 = 10
Al tomar el 6to elemento del arreglo B, ya que estamos ingresando desde el arreglo A al arreglo B, suma = 10 + 1 + 1 = 12
Al tomar el 7mo elemento del arreglo A, como estamos ingresando del arreglo B al arreglo A, suma = 12 + 1 + 1 = 14
Al tomar el octavo elemento del arreglo B, mientras ingresamos del arreglo A al arreglo B, suma = 14 + 1 + 1 = 16
Al tomar el noveno elemento del arreglo A, mientras ingresamos del arreglo B al arreglo A, suma = 16 + 1 + 1 = 18.
Enfoque: Usaremos Programación Dinámica para resolver este problema. A continuación se muestran los pasos:
- Cree una array 2D dp[][] de N filas y dos columnas e inicialice todos los elementos de dp hasta el infinito .
- Puede haber 4 casos posibles de agregar los elementos de ambas arrays:
- Agregar un elemento de la array a[] cuando el elemento agregado anteriormente es de la array a[].
- Agregar un elemento de la array a[] cuando el elemento agregado anteriormente es de la array b[]. En este caso hay una penalización de sumar el entero C con el resultado.
- Agregar un elemento de la array b[] cuando el elemento agregado anteriormente es de la array b[].
- Agregar un elemento de la array b[] cuando el elemento agregado anteriormente es de la array a[]. En este caso hay una penalización de sumar el entero C con el resultado.
- Actualice la array dp cada vez con el valor mínimo de las cuatro condiciones anteriores.
- El mínimo de dp[n-1][0] y dp[n-1][1] es la suma mínima total de seleccionar N elementos.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function that prints minimum sum
// after selecting N elements
void minimumSum(int a[], int b[],
int c, int n)
{
// Initialise the dp array
vector<vector<int> > dp(n,
vector<int>(2,
1e6));
// Base Case
dp[0][0] = a[0];
dp[0][1] = b[0];
for (int i = 1; i < n; i++) {
// Adding the element of array a if
// previous element is also from array a
dp[i][0] = min(dp[i][0],
dp[i - 1][0] + a[i]);
// Adding the element of array a if
// previous element is from array b
dp[i][0] = min(dp[i][0],
dp[i - 1][1] + a[i] + c);
// Adding the element of array b if
// previous element is from array a
// with an extra penalty of integer C
dp[i][1] = min(dp[i][1],
dp[i - 1][0] + b[i] + c);
// Adding the element of array b if
// previous element is also from array b
dp[i][1] = min(dp[i][1],
dp[i - 1][1] + b[i]);
}
// Print the minimum sum
cout << min(dp[n - 1][0],
dp[n - 1][1])
<< "\n";
}
// Driver Code
int main()
{
// Given array arr1[] and arr2[]
int arr1[] = { 7, 6, 18, 6, 16,
18, 1, 17, 17 };
int arr2[] = { 6, 9, 3, 10, 9,
1, 10, 1, 5 };
// Given cost
int C = 2;
int N = sizeof(arr1) / sizeof(arr1[0]);
// Function Call
minimumSum(arr1, arr2, C, N);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function that prints minimum sum
// after selecting N elements
static void minimumSum(int a[], int b[],
int c, int n)
{
// Initialise the dp array
int [][]dp = new int[n][2];
for(int i = 0; i < n; i++)
{
for(int j = 0; j < 2; j++)
{
dp[i][j] = (int) 1e6;
}
}
// Base Case
dp[0][0] = a[0];
dp[0][1] = b[0];
for(int i = 1; i < n; i++)
{
// Adding the element of array a if
// previous element is also from array a
dp[i][0] = Math.min(dp[i][0],
dp[i - 1][0] + a[i]);
// Adding the element of array a if
// previous element is from array b
dp[i][0] = Math.min(dp[i][0],
dp[i - 1][1] + a[i] + c);
// Adding the element of array b if
// previous element is from array a
// with an extra penalty of integer C
dp[i][1] = Math.min(dp[i][1],
dp[i - 1][0] + b[i] + c);
// Adding the element of array b if
// previous element is also from array b
dp[i][1] = Math.min(dp[i][1],
dp[i - 1][1] + b[i]);
}
// Print the minimum sum
System.out.print(Math.min(dp[n - 1][0],
dp[n - 1][1]) + "\n");
}
// Driver Code
public static void main(String[] args)
{
// Given array arr1[] and arr2[]
int arr1[] = { 7, 6, 18, 6, 16,
18, 1, 17, 17 };
int arr2[] = { 6, 9, 3, 10, 9,
1, 10, 1, 5 };
// Given cost
int C = 2;
int N = arr1.length;
// Function call
minimumSum(arr1, arr2, C, N);
}
}
// This code is contributed by gauravrajput1
Python3
# Python3 program for the above approach # Function that prints minimum sum # after selecting N elements def minimumSum(a, b, c, n): # Initialise the dp array dp = [[1e6 for i in range(2)] for j in range(n)] # Base Case dp[0][0] = a[0] dp[0][1] = b[0] for i in range(1, n): # Adding the element of array a if # previous element is also from array a dp[i][0] = min(dp[i][0], dp[i - 1][0] + a[i]) # Adding the element of array a if # previous element is from array b dp[i][0] = min(dp[i][0], dp[i - 1][1] + a[i] + c) # Adding the element of array b if # previous element is from array a # with an extra penalty of integer C dp[i][1] = min(dp[i][1], dp[i - 1][0] + b[i] + c) # Adding the element of array b if # previous element is also from array b dp[i][1] = min(dp[i][1], dp[i - 1][1] + b[i]) # Print the minimum sum print(min(dp[n - 1][0], dp[n - 1][1])) # Driver code if __name__ == '__main__': # Given array arr[] arr1 = [ 7, 6, 18, 6, 16, 18, 1, 17, 17 ] arr2 = [ 6, 9, 3, 10, 9, 1, 10, 1, 5 ] # Given cost C = 2 N = len(arr1) # Function Call minimumSum(arr1, arr2, C, N) # This code is contributed by Shivam Singh
C#
// C# program for the above approach
using System;
class GFG{
// Function that prints minimum sum
// after selecting N elements
static void minimumSum(int []a, int []b,
int c, int n)
{
// Initialise the dp array
int [,]dp = new int[n, 2];
for(int i = 0; i < n; i++)
{
for(int j = 0; j < 2; j++)
{
dp[i, j] = (int)1e6;
}
}
// Base Case
dp[0, 0] = a[0];
dp[0, 1] = b[0];
for(int i = 1; i < n; i++)
{
// Adding the element of array a if
// previous element is also from array a
dp[i, 0] = Math.Min(dp[i, 0],
dp[i - 1, 0] + a[i]);
// Adding the element of array a if
// previous element is from array b
dp[i, 0] = Math.Min(dp[i, 0],
dp[i - 1, 1] + a[i] + c);
// Adding the element of array b if
// previous element is from array a
// with an extra penalty of integer C
dp[i, 1] = Math.Min(dp[i, 1],
dp[i - 1, 0] + b[i] + c);
// Adding the element of array b if
// previous element is also from array b
dp[i, 1] = Math.Min(dp[i, 1],
dp[i - 1, 1] + b[i]);
}
// Print the minimum sum
Console.Write(Math.Min(dp[n - 1, 0],
dp[n - 1, 1]) + "\n");
}
// Driver Code
public static void Main(String[] args)
{
// Given array arr1[] and arr2[]
int []arr1 = { 7, 6, 18, 6, 16,
18, 1, 17, 17 };
int []arr2 = { 6, 9, 3, 10, 9,
1, 10, 1, 5 };
// Given cost
int C = 2;
int N = arr1.Length;
// Function call
minimumSum(arr1, arr2, C, N);
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// JavaScript program for the above approach
// Function that prints minimum sum
// after selecting N elements
function minimumSum(a, b, c, n)
{
// Initialise the dp array
let dp = new Array(n);
for (var i = 0; i < dp.length; i++) {
dp[i] = new Array(2);
}
for(let i = 0; i < n; i++)
{
for(let j = 0; j < 2; j++)
{
dp[i][j] = 1e6;
}
}
// Base Case
dp[0][0] = a[0];
dp[0][1] = b[0];
for(let i = 1; i < n; i++)
{
// Adding the element of array a if
// previous element is also from array a
dp[i][0] = Math.min(dp[i][0],
dp[i - 1][0] + a[i]);
// Adding the element of array a if
// previous element is from array b
dp[i][0] = Math.min(dp[i][0],
dp[i - 1][1] + a[i] + c);
// Adding the element of array b if
// previous element is from array a
// with an extra penalty of integer C
dp[i][1] = Math.min(dp[i][1],
dp[i - 1][0] + b[i] + c);
// Adding the element of array b if
// previous element is also from array b
dp[i][1] = Math.min(dp[i][1],
dp[i - 1][1] + b[i]);
}
// Print the minimum sum
document.write(Math.min(dp[n - 1][0],
dp[n - 1][1]) + "<br/>");
}
// Driver Code
// Given array arr1[] and arr2[]
let arr1 = [ 7, 6, 18, 6, 16,
18, 1, 17, 17 ];
let arr2 = [ 6, 9, 3, 10, 9,
1, 10, 1, 5 ];
// Given cost
let C = 2;
let N = arr1.length;
// Function call
minimumSum(arr1, arr2, C, N);
</script>
49
Complejidad de tiempo: O(N)
Publicación traducida automáticamente
Artículo escrito por nitinkr8991 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA