Maximice el costo de vaciar una array eliminando subarreglos contiguos de elementos iguales

Posted on by Rudeus Greyrat

Dada una array arr[] que consta de N enteros y un entero M , la tarea es encontrar el costo máximo que se puede obtener realizando la siguiente operación cualquier número de veces. 

En una operación, elija K elementos contiguos con el mismo valor (donde K ≥ 1) y elimínelos; el costo de esta operación es K *  M.

Ejemplos: 

Entrada: arr[] = {1, 3, 2, 2, 2, 3, 4, 3, 1}, M = 3 
Salida: 27 
Explicación: 
Paso 1: elimine tres 2 contiguos para modificar arr[] = {1, 3, 3, 4, 3, 1}. Costo = 3 * 3 = 9 
Paso 2: elimine 4 para modificar arr[] = {1, 3, 3, 3, 1}. Costo = 9 + 1 * 3 = 12 
Paso 3: elimine tres 3 contiguos para modificar arr[] = {1, 1}. Costo = 12 + 3 * 3 = 21 
Paso 4: elimine dos 1 contiguos para modificar arr[] = {}. Costo = 21 + 2 * 3 = 27

Entrada: arr[] = {1, 2, 3, 4, 5, 6, 7}, M = 2 
Salida: 14

Enfoque: Este problema se puede resolver usando Programación Dinámica . A continuación se muestran los pasos:

  1. Inicialice una array 3D dp[][][] tal que dp[left][right][count] , donde left y right indican la operación entre índices [left, right] y count es el número de elementos a la izquierda de arr[ left] que tiene el mismo valor que el de arr[left] y el conteo excluye arr[left] .
  2. Ahora hay las siguientes dos opciones posibles: 
    • Terminar la secuencia para eliminar los elementos del mismo valor, incluido el elemento inicial (es decir, arr[left] ) y luego continuar desde el siguiente elemento en adelante.
    • Continúe la secuencia para buscar entre los índices [izquierda + 1, derecha] elementos que tengan el mismo valor que arr[izquierda] (digamos índice i ), esto nos permite continuar la secuencia.
  3. Realice llamadas recursivas desde la nueva secuencia y continúe el proceso para la secuencia anterior.
  4. Imprime el costo máximo después de todos los pasos anteriores.

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;
 
// Initialize dp array
int dp[101][101][101];
 
// Function that removes elements
// from array to maximize the cost
int helper(int arr[], int left, int right,
           int count, int m)
{
    // Base case
    if (left > right)
        return 0;
 
    // Check if an answer is stored
    if (dp[left][right][count] != -1) {
        return dp[left][right][count];
    }
 
    // Deleting count + 1 i.e. including
    // the first element and starting a
    // new sequence
    int ans = (count + 1) * m
              + helper(arr, left + 1,
                       right, 0, m);
 
    for (int i = left + 1;
         i <= right; ++i) {
 
        if (arr[i] == arr[left]) {
 
            // Removing [left + 1, i - 1]
            // elements to continue with
            // previous sequence
            ans = max(
                ans,
                helper(arr, left + 1,
                       i - 1, 0, m)
                    + helper(arr, i, right,
                             count + 1, m));
        }
    }
 
    // Store the result
    dp[left][right][count] = ans;
 
    // Return answer
    return ans;
}
 
// Function to remove the elements
int maxPoints(int arr[], int n, int m)
{
    int len = n;
    memset(dp, -1, sizeof(dp));
 
    // Function Call
    return helper(arr, 0, len - 1, 0, m);
}
 
// Driver Code
int main()
{
    // Given array
    int arr[] = { 1, 3, 2, 2, 2, 3, 4, 3, 1 };
 
    int M = 3;
 
    int N = sizeof(arr) / sizeof(arr[0]);
 
    // Function Call
    cout << maxPoints(arr, N, M);
    return 0;
}

Java

// Java program for the above approach
import java.util.*;
 
class GFG{
 
// Initialize dp array
static int [][][]dp = new int[101][101][101];
 
// Function that removes elements
// from array to maximize the cost
static int helper(int arr[], int left, int right,
                  int count, int m)
{
     
    // Base case
    if (left > right)
        return 0;
 
    // Check if an answer is stored
    if (dp[left][right][count] != -1)
    {
        return dp[left][right][count];
    }
 
    // Deleting count + 1 i.e. including
    // the first element and starting a
    // new sequence
    int ans = (count + 1) * m +
             helper(arr, left + 1,
                    right, 0, m);
 
    for(int i = left + 1; i <= right; ++i)
    {
        if (arr[i] == arr[left])
        {
             
            // Removing [left + 1, i - 1]
            // elements to continue with
            // previous sequence
            ans = Math.max(ans,
                  helper(arr, left + 1,
                         i - 1, 0, m) +
                  helper(arr, i, right,
                         count + 1, m));
        }
    }
 
    // Store the result
    dp[left][right][count] = ans;
 
    // Return answer
    return ans;
}
 
// Function to remove the elements
static int maxPoints(int arr[], int n, int m)
{
    int len = n;
    for(int i = 0; i < 101; i++)
    {
        for(int j = 0; j < 101; j++)
        {
            for(int k = 0; k < 101; k++)
                dp[i][j][k] = -1;
        }
    }
 
    // Function call
    return helper(arr, 0, len - 1, 0, m);
}
 
// Driver Code
public static void main(String[] args)
{
     
    // Given array
    int arr[] = { 1, 3, 2, 2, 2, 3, 4, 3, 1 };
 
    int M = 3;
 
    int N = arr.length;
 
    // Function call
    System.out.print(maxPoints(arr, N, M));
}
}
 
// This code is contributed by Amit Katiyar

Python3

# Python3 program for
# the above approach
 
# Initialize dp array
dp = [[[-1 for x in range(101)]
            for y in range(101)]
            for z in range(101)]
  
# Function that removes elements
# from array to maximize the cost
def helper(arr, left,
           right, count, m):
 
  # Base case
  if (left > right):
    return 0
 
  # Check if an answer is stored
  if (dp[left][right][count] != -1):
    return dp[left][right][count]
 
  # Deleting count + 1 i.e. including
  # the first element and starting a
  # new sequence
  ans = ((count + 1) * m +
          helper(arr, left + 1,
                 right, 0, m))
 
  for i in range (left + 1,
                  right + 1):
 
    if (arr[i] == arr[left]):
 
      # Removing [left + 1, i - 1]
      # elements to continue with
      # previous sequence
      ans = (max(ans, helper(arr, left + 1,
                             i - 1, 0, m) +
                         helper(arr, i, right,
                              count + 1, m)))
 
      # Store the result
      dp[left][right][count] = ans
 
      # Return answer
      return ans
  
# Function to remove the elements
def maxPoints(arr, n, m):
  length = n
  global dp
 
  # Function Call
  return helper(arr, 0,
                length - 1, 0, m)
  
# Driver Code
if __name__ == "__main__":
 
  # Given array
  arr = [1, 3, 2, 2,
         2, 3, 4, 3, 1]
  M = 3
  N = len(arr)
 
  # Function Call
  print(maxPoints(arr, N, M))
     
# This code is contributed by Chitranayal

C#

// C# program for the above approach
using System;
 
class GFG{
 
// Initialize dp array
static int [,,]dp = new int[101, 101, 101];
 
// Function that removes elements
// from array to maximize the cost
static int helper(int []arr, int left, int right,
                  int count, int m)
{
     
    // Base case
    if (left > right)
        return 0;
 
    // Check if an answer is stored
    if (dp[left, right, count] != -1)
    {
        return dp[left, right, count];
    }
 
    // Deleting count + 1 i.e. including
    // the first element and starting a
    // new sequence
    int ans = (count + 1) * m +
              helper(arr, left + 1,
                    right, 0, m);
 
    for(int i = left + 1; i <= right; ++i)
    {
        if (arr[i] == arr[left])
        {
             
            // Removing [left + 1, i - 1]
            // elements to continue with
            // previous sequence
            ans = Math.Max(ans,
                  helper(arr, left + 1,
                         i - 1, 0, m) +
                  helper(arr, i, right,
                         count + 1, m));
        }
    }
 
    // Store the result
    dp[left, right, count] = ans;
 
    // Return answer
    return ans;
}
 
// Function to remove the elements
static int maxPoints(int []arr, int n, int m)
{
    int len = n;
    for(int i = 0; i < 101; i++)
    {
        for(int j = 0; j < 101; j++)
        {
            for(int k = 0; k < 101; k++)
                dp[i, j, k] = -1;
        }
    }
 
    // Function call
    return helper(arr, 0, len - 1, 0, m);
}
 
// Driver Code
public static void Main(String[] args)
{
     
    // Given array
    int []arr = { 1, 3, 2, 2, 2, 3, 4, 3, 1 };
 
    int M = 3;
 
    int N = arr.Length;
 
    // Function call
    Console.Write(maxPoints(arr, N, M));
}
}
 
// This code is contributed by Amit Katiyar

Javascript

<script>
 
// Javascript program for the above approach
 
// Initialize dp array
let dp = new Array(101);
for(let i = 0; i < 101; i++)
{
    dp[i] = new Array(101);
    for(let j = 0; j < 101; j++)
    {
        dp[i][j] = new Array(101);
        for(let k = 0; k < 101; k++)
        {
            dp[i][j][k] = -1;
        }
    }
}
 
// Function that removes elements
// from array to maximize the cost
function helper(arr, left, right, count, m)
{
     
    // Base case
    if (left > right)
        return 0;
 
    // Check if an answer is stored
    if (dp[left][right][count] != -1)
    {
        return dp[left][right][count];
    }
 
    // Deleting count + 1 i.e. including
    // the first element and starting a
    // new sequence
    let ans = (count + 1) * m +
              helper(arr, left + 1,
                     right, 0, m);
 
    for(let i = left + 1; i <= right; ++i)
    {
        if (arr[i] == arr[left])
        {
             
            // Removing [left + 1, i - 1]
            // elements to continue with
            // previous sequence
            ans = Math.max(ans,
                  helper(arr, left + 1,
                         i - 1, 0, m) +
                  helper(arr, i, right,
                         count + 1, m));
        }
    }
 
    // Store the result
    dp[left][right][count] = ans;
 
    // Return answer
    return ans;
}
 
// Function to remove the elements
function maxPoints(arr, n, m)
{
    let len = arr.length;
     
    // Function call
    return helper(arr, 0, len - 1, 0, m);
}
 
// Driver Code
 
// Given array
let arr = [ 1, 3, 2, 2, 2, 3, 4, 3, 1 ];
let M = 3;
let N = arr.length;
 
// Function call
document.write(maxPoints(arr, N, M));
 
// This code is contributed by avanitrachhadiya2155
 
</script>
Producción: 

27

Complejidad de Tiempo: O(N 4 ) 
Espacio Auxiliar: O(N 3 ) 

Publicación traducida automáticamente

Artículo escrito por rishabhtyagi2306 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 *