Dado un arreglo arr[] de tamaño N y un entero K , la tarea es encontrar el costo mínimo requerido para reducir el arreglo dado a un solo elemento, donde el costo de reemplazar K elementos consecutivos del arreglo por su suma es igual a la suma de los K elementos consecutivos. Si no es posible reducir la array dada a un solo elemento, imprima -1 .
Ejemplos:
Entrada: arr[] = {3, 5, 1, 2, 6}, K = 3
Salida: 25
Explicación:
Reemplazar {arr[1], arr[2], arr[3]} modifica arr[] = {3 , 8, 6}. Costo = 8
Reemplazar {arr[0], arr[1], arr[2]} modifica arr[] = {17}. Costo = 17.
Por lo tanto, el costo total de fusionar todos los elementos de la array en uno = 8 + 17 = 25Entrada: arr[] = {3, 2, 4, 1}, K = 3
Salida: -1
La combinación de cualquier K (=3) elementos de array consecutivos dejó 2 elementos en la array.
Por lo tanto, la salida requerida es -1.
Planteamiento: El problema se puede resolver usando programación Dinámica . La siguiente es la relación de recurrencia:
Dado que el tamaño de la array se reduce en (K – 1) después de cada operación de reemplazo,
dp[i][j] = min(dp[i][x], dp[x+1][j]), X = i + entero * (K – 1)
donde, dp[i][j] almacena el costo mínimo para fusionar el número máximo de elementos de array en el intervalo [i, j] con el elemento más a la izquierda arr[i] siempre involucrado en la fusión si posible
Siga los pasos a continuación para resolver el problema:
- Si (N – 1) % (K – 1) != 0 entonces imprima -1 .
- Inicialice una array , diga prefixSum[] para almacenar la suma del prefijo de la array dada.
- Inicialice una array 2D , digamos dp[][] , donde dp[i][j] almacena el costo mínimo para fusionar la cantidad máxima de elementos de la array en el intervalo [i, j] .
- Complete la tabla de DP utilizando la relación mencionada anteriormente entre los estados de DP.
- Finalmente, imprima el valor de dp[0][N – 1] .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement
// the above approach
#include<bits/stdc++.h>
using namespace std;
// Function to find the minimum cost
// to reduce given array to a single
// element by replacing consecutive
// K array elements
int minimumCostToMergeK(int arr[], int K, int N)
{
// If (N - 1) is not
// multiple of (K - 1)
if ((N - 1) % (K - 1) != 0)
{
return -1;
}
// Store prefix sum of the array
int prefixSum[N + 1] = {0};
// Iterate over the range [1, N]
for(int i = 1; i < (N + 1); i++)
{
// Update prefixSum[i]
prefixSum[i] = (prefixSum[i - 1] + arr[i - 1]);
}
// dp[i][j]: Store minimum cost to
// merge array elements interval [i, j]
int dp[N][N];
memset(dp, 0, sizeof(dp));
// L: Stores length of interval [i, j]
for(int L = K; L < (N + 1); L++)
{
// Iterate over each interval
// [i, j] of length L in in [0, N]
for(int i = 0; i < (N - L + 1); i++)
{
// Stores index of last element
// of the interval [i, j]
int j = i + L - 1;
// If L is greater than K
if (L > K)
{
int temp = INT_MAX;
for(int x = i; x < j; x += K - 1)
{
temp = min(temp, dp[i][x] +
dp[x + 1][j]);
}
// Update dp[i][j]
dp[i][j] = temp;
}
// If (L - 1) is multiple of (K - 1)
if ((L - 1) % (K - 1) == 0)
{
// Update dp[i][j]
dp[i][j] += (prefixSum[j + 1] -
prefixSum[i]);
}
}
}
// Return dp[0][N - 1]
return dp[0][N - 1];
}
// Driver Code
int main()
{
int arr[] = { 3, 5, 1, 2, 6 };
int K = 3;
// Stores length of arr
int N = sizeof(arr) / sizeof(arr[0]);
cout << minimumCostToMergeK(arr, K, N);
}
// This code is contributed by rag2127
Java
// Java program to implement
// the above approach
import java.util.*;
class GFG
{
// Function to find the minimum cost
// to reduce given array to a single
// element by replacing consecutive
// K array elements
static int minimumCostToMergeK(int arr[], int K, int N)
{
// If (N - 1) is not
// multiple of (K - 1)
if ((N - 1) % (K - 1) != 0)
{
return -1;
}
// Store prefix sum of the array
int []prefixSum = new int[N + 1];
// Iterate over the range [1, N]
for(int i = 1; i < (N + 1); i++)
{
// Update prefixSum[i]
prefixSum[i] = (prefixSum[i - 1] + arr[i - 1]);
}
// dp[i][j]: Store minimum cost to
// merge array elements interval [i, j]
int [][]dp = new int[N][N];
// L: Stores length of interval [i, j]
for(int L = K; L < (N + 1); L++)
{
// Iterate over each interval
// [i, j] of length L in in [0, N]
for(int i = 0; i < (N - L + 1); i++)
{
// Stores index of last element
// of the interval [i, j]
int j = i + L - 1;
// If L is greater than K
if (L > K)
{
int temp = Integer.MAX_VALUE;
for(int x = i; x < j; x += K - 1)
{
temp = Math.min(temp, dp[i][x] +
dp[x + 1][j]);
}
// Update dp[i][j]
dp[i][j] = temp;
}
// If (L - 1) is multiple of (K - 1)
if ((L - 1) % (K - 1) == 0)
{
// Update dp[i][j]
dp[i][j] += (prefixSum[j + 1] -
prefixSum[i]);
}
}
}
// Return dp[0][N - 1]
return dp[0][N - 1];
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 3, 5, 1, 2, 6 };
int K = 3;
// Stores length of arr
int N = arr.length;
System.out.print(minimumCostToMergeK(arr, K, N));
}
}
// This code is contributed by shikhasingrajput
Python3
# Python3 program to implement # the above approach # Function to find the minimum cost # to reduce given array to a single # element by replacing consecutive # K array elements def minimumCostToMergeK(arr, K): # Stores length of arr N = len(arr) # If (N - 1) is not # multiple of (K - 1) if (N - 1) % (K - 1) != 0: return -1 # Store prefix sum of the array prefixSum = [0] * (N + 1) # Iterate over the range [1, N] for i in range(1, N + 1): # Update prefixSum[i] prefixSum[i] = (prefixSum[i - 1] + arr[i - 1]) # dp[i][j]: Store minimum cost to # merge array elements interval [i, j] dp = [[0]*N for _ in range(N)] # L: Stores length of interval [i, j] for L in range(K, N + 1): # Iterate over each interval # [i, j] of length L in in [0, N] for i in range(N - L + 1): # Stores index of last element # of the interval [i, j] j = i + L - 1 # If L is greater than K if L > K: # Update dp[i][j] dp[i][j] =( min([dp[i][x] + dp[x + 1][j] for x in range(i, j, K-1)])) # If (L - 1) is multiple of (K - 1) if (L - 1) % (K - 1) == 0: # Update dp[i][j] dp[i][j] += (prefixSum[j + 1] - prefixSum[i]) # Return dp[0][N - 1] return dp[0][N-1] if __name__ == "__main__": arr = [3, 5, 1, 2, 6] K = 3 print(minimumCostToMergeK(arr, K))
C#
// C# program to implement
// the above approach
using System;
class GFG
{
// Function to find the minimum cost
// to reduce given array to a single
// element by replacing consecutive
// K array elements
static int minimumCostToMergeK(int []arr, int K, int N)
{
// If (N - 1) is not
// multiple of (K - 1)
if ((N - 1) % (K - 1) != 0)
{
return -1;
}
// Store prefix sum of the array
int []prefixSum = new int[N + 1];
// Iterate over the range [1, N]
for(int i = 1; i < (N + 1); i++)
{
// Update prefixSum[i]
prefixSum[i] = (prefixSum[i - 1] + arr[i - 1]);
}
// dp[i,j]: Store minimum cost to
// merge array elements interval [i, j]
int [,]dp = new int[N,N];
// L: Stores length of interval [i, j]
for(int L = K; L < (N + 1); L++)
{
// Iterate over each interval
// [i, j] of length L in in [0, N]
for(int i = 0; i < (N - L + 1); i++)
{
// Stores index of last element
// of the interval [i, j]
int j = i + L - 1;
// If L is greater than K
if (L > K)
{
int temp = int.MaxValue;
for(int x = i; x < j; x += K - 1)
{
temp = Math.Min(temp, dp[i, x] +
dp[x + 1, j]);
}
// Update dp[i,j]
dp[i, j] = temp;
}
// If (L - 1) is multiple of (K - 1)
if ((L - 1) % (K - 1) == 0)
{
// Update dp[i,j]
dp[i, j] += (prefixSum[j + 1] -
prefixSum[i]);
}
}
}
// Return dp[0,N - 1]
return dp[0, N - 1];
}
// Driver Code
public static void Main(String[] args)
{
int []arr = { 3, 5, 1, 2, 6 };
int K = 3;
// Stores length of arr
int N = arr.Length;
Console.Write(minimumCostToMergeK(arr, K, N));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// javascript program to implement
// the above approach
// Function to find the minimum cost
// to reduce given array to a single
// element by replacing consecutive
// K array elements
function minimumCostToMergeK(arr , K , N)
{
// If (N - 1) is not
// multiple of (K - 1)
if ((N - 1) % (K - 1) != 0) {
return -1;
}
// Store prefix sum of the array
var prefixSum = Array(N + 1).fill(0);
// Iterate over the range [1, N]
for (i = 1; i < (N + 1); i++) {
// Update prefixSum[i]
prefixSum[i] = (prefixSum[i - 1] + arr[i - 1]);
}
// dp[i][j]: Store minimum cost to
// merge array elements interval [i, j]
var dp = Array(N);
for( i = 0; i<N;i++)
dp[i] = Array(N).fill(0);
// L: Stores length of interval [i, j]
for (L = K; L < (N + 1); L++) {
// Iterate over each interval
// [i, j] of length L in in [0, N]
for (i = 0; i < (N - L + 1); i++) {
// Stores index of last element
// of the interval [i, j]
var j = i + L - 1;
// If L is greater than K
if (L > K) {
var temp = Number.MAX_VALUE;
for (x = i; x < j; x += K - 1) {
temp = Math.min(temp, dp[i][x] + dp[x + 1][j]);
}
// Update dp[i][j]
dp[i][j] = temp;
}
// If (L - 1) is multiple of (K - 1)
if ((L - 1) % (K - 1) == 0) {
// Update dp[i][j]
dp[i][j] += (prefixSum[j + 1] - prefixSum[i]);
}
}
}
// Return dp[0][N - 1]
return dp[0][N - 1];
}
// Driver Code
var arr = [ 3, 5, 1, 2, 6 ];
var K = 3;
// Stores length of arr
var N = arr.length;
document.write(minimumCostToMergeK(arr, K, N));
// This code is contributed by todaysgaurav
</script>
Producción:
25
Complejidad de Tiempo: O(N 2 * K)
Espacio Auxiliar: O(N 2 )
Publicación traducida automáticamente
Artículo escrito por saikumarkudikala y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA