Dada una array binaria arr[] y una array de valores val[] . La tarea es encontrar las divisiones máximas posibles de la array binaria que se pueden hacer de manera que cada segmento contenga un número igual de 0 y 1 utilizando como máximo k monedas. Cada división cuesta (val[i] – val[j]) 2 , donde i y j son los índices adyacentes del segmento dividido.
Ejemplos:
Entrada: arr[] = {0, 1, 0, 0, 1, 1}, val[] = {2, 5, 1, 3, 6, 10}, k = 20
Salida: 1
Explicación: se pueden hacer divisiones de la siguiente manera: 0 1 0 0 1 1 y costo = (5 – 1) 2 = 16 ≤ 20.Entrada: arr[] = {1, 0, 0, 1, 0, 1, 1, 0}, val[] = {9, 7, 5, 2, 4, 12, 3, 1], k = 10
Salida : 2
Explicación: Las divisiones se pueden hacer de la siguiente manera: 1 0 0 1 0 1 1 0
Enfoque: la tarea se puede resolver mediante programación dinámica (enfoque de arriba hacia abajo).
Siga los pasos a continuación:
- Inicialice una array 2d, digamos dp de dimensiones K * N.
- Para cada índice, hay dos opciones, si hacer un corte en ese índice o no hacer un corte en ese índice, siempre que el número de ceros y unos sea igual.
- Memoize los valores, para ser utilizados de nuevo
- Maximice el valor de count_splits para obtener los cortes máximos resultantes.
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;
int dp[1001][1001];
// Function to find maximum possible splits
// in atmost k coins such that each
// segment contains equal number of 0 and 1
int maximumSplits(int arr[], int val[],
int k, int N)
{
// Base Case
if (k < 0) {
return INT_MIN;
}
// If already have a stored value
// return it
if (dp[k][N] != -1) {
return dp[k][N];
}
// Count for zeros and ones
int zero = 0, one = 0;
// Count for number of splits
int count_split = 0;
int i;
// Iterate over the array and
// search for zeros and ones
for (i = N - 1; i > 0; i--) {
arr[i] == 0 ? zero++ : one++;
// If count of zeros is equal to
// count of ones
if (zero == one) {
// Store the maximum possible one
count_split = max(
count_split,
1
+ maximumSplits(
arr, val,
k - pow(val[i]
- val[i - 1],
2),
i));
}
}
// If index is at 0, find if
// it is zero or one and
// increment the count
if (i == 0) {
arr[0] == 0 ? zero++ : one++;
// If count of zero is not equal to
// count of one, re-initialize
// count_split with 0
if (zero != one) {
count_split = 0;
}
}
// Store the returned value in dp[]
return dp[k][N] = count_split;
}
// Driver Code
int main()
{
int arr[] = { 1, 0, 0, 1, 0, 1, 1, 0 };
int val[] = { 9, 7, 5, 2, 4, 12, 3, 1 };
int k = 10;
int N = sizeof(arr) / sizeof(arr[0]);
memset(dp, -1, sizeof(dp));
cout << maximumSplits(arr, val, k, N);
return 0;
}
Java
// Java program for the above approach
public class GFG
{
static int[][] dp = new int[1001][1001];
// Function to find maximum possible splits
// in atmost k coins such that each
// segment contains equal number of 0 and 1
static int maximumSplits(int[] arr, int[] val,
int k, int N)
{
// Base Case
if (k < 0) {
return Integer.MIN_VALUE;
}
// If already have a stored value
// return it
if (dp[k][N] != -1) {
return dp[k][N];
}
// Count for zeros and ones
int zero = 0, one = 0;
// Count for number of splits
int count_split = 0;
int i;
// Iterate over the array and
// search for zeros and ones
for (i = N - 1; i > 0; i--) {
if(arr[i] == 0)
zero++;
else
one++;
// If count of zeros is equal to
// count of ones
if (zero == one) {
// Store the maximum possible one
count_split = Math.max(
count_split,
1
+ maximumSplits(
arr, val,
k - (int)Math.pow(val[i]
- val[i - 1],
2),
i));
}
}
// If index is at 0, find if
// it is zero or one and
// increment the count
if (i == 0) {
if(arr[0] == 0)
zero++;
else
one++;
// If count of zero is not equal to
// count of one, re-initialize
// count_split with 0
if (zero != one) {
count_split = 0;
}
}
// Store the returned value in dp[]
return dp[k][N] = count_split;
}
// Driver code
public static void main(String[] args)
{
int[] arr = { 1, 0, 0, 1, 0, 1, 1, 0 };
int[] val = { 9, 7, 5, 2, 4, 12, 3, 1 };
int k = 10;
int N = arr.length;
int i, j;
for(i=0;i<1001;i++)
{
for(j=0;j<1001;j++)
{
dp[i][j] = -1;
}
}
System.out.println(maximumSplits(arr, val, k, N));
}
}
// This code is contributed by AnkThon
Python3
# Python Program to implement # the above approach dp = [0] * 1001 for i in range(len(dp)): dp[i] = [-1] * 1001 # Function to find maximum possible splits # in atmost k coins such that each # segment contains equal number of 0 and 1 def maximumSplits(arr, val, k, N): # Base Case if (k < 0): return 10 ** (-9) # If already have a stored value # return it if (dp[k][N] != -1) : return dp[k][N] # Count for zeros and ones zero = 0 one = 0 # Count for number of splits count_split = 0 # Iterate over the array and # search for zeros and ones for i in range(N - 1, 0, -1): if (arr[i] == 0): zero += 1 else: one += 1 # If count of zeros is equal to # count of ones if (zero == one): # Store the maximum possible one count_split = max( count_split, 1 + maximumSplits( arr, val, k - pow(val[i] - val[i - 1], 2), i)) # If index is at 0, find if # it is zero or one and # increment the count if (i == 0): if (arr[i] == 0): zero += 1 else: one -= 1 # If count of zero is not equal to # count of one, re-initialize # count_split with 0 if (zero != one): count_split = 0 # Store the returned value in dp[] dp[k][N] = count_split return dp[k][N] # Driver Code arr = [1, 0, 0, 1, 0, 1, 1, 0] val = [9, 7, 5, 2, 4, 12, 3, 1] k = 10 N = len(arr) print(maximumSplits(arr, val, k, N)) # This code is contributed by Saurabh Jaiswal
C#
// C# program for the above approach
using System;
public class GFG
{
static int[,] dp = new int[1001, 1001];
// Function to find maximum possible splits
// in atmost k coins such that each
// segment contains equal number of 0 and 1
static int maximumSplits(int[] arr, int[] val,
int k, int N)
{
// Base Case
if (k < 0) {
return Int32.MinValue;
}
// If already have a stored value
// return it
if (dp[k, N] != -1) {
return dp[k, N];
}
// Count for zeros and ones
int zero = 0, one = 0;
// Count for number of splits
int count_split = 0;
int i;
// Iterate over the array and
// search for zeros and ones
for (i = N - 1; i > 0; i--) {
if(arr[i] == 0)
zero++;
else
one++;
// If count of zeros is equal to
// count of ones
if (zero == one) {
// Store the maximum possible one
count_split = Math.Max(
count_split,
1
+ maximumSplits(
arr, val,
k - (int)Math.Pow(val[i]
- val[i - 1],
2),
i));
}
}
// If index is at 0, find if
// it is zero or one and
// increment the count
if (i == 0) {
if(arr[0] == 0)
zero++;
else
one++;
// If count of zero is not equal to
// count of one, re-initialize
// count_split with 0
if (zero != one) {
count_split = 0;
}
}
// Store the returned value in dp[]
return dp[k, N] = count_split;
}
// Driver code
public static void Main(String[] args)
{
int[] arr = { 1, 0, 0, 1, 0, 1, 1, 0 };
int[] val = { 9, 7, 5, 2, 4, 12, 3, 1 };
int k = 10;
int N = arr.Length;
int i, j;
for(i=0;i<1001;i++)
{
for(j=0;j<1001;j++)
{
dp[i, j] = -1;
}
}
Console.WriteLine(maximumSplits(arr, val, k, N));
}
}
// This code is contributed by sanjoy_62.
Javascript
<script>
// JavaScript Program to implement
// the above approach
let dp = new Array(1001);
for (let i = 0; i < dp.length; i++) {
dp[i] = new Array(1001).fill(-1);
}
// Function to find maximum possible splits
// in atmost k coins such that each
// segment contains equal number of 0 and 1
function maximumSplits(arr, val,
k, N)
{
// Base Case
if (k < 0) {
return Number.MIN_VALUE;
}
// If already have a stored value
// return it
if (dp[k][N] != -1) {
return dp[k][N];
}
// Count for zeros and ones
let zero = 0, one = 0;
// Count for number of splits
let count_split = 0;
let i;
// Iterate over the array and
// search for zeros and ones
for (i = N - 1; i > 0; i--) {
arr[i] == 0 ? zero++ : one++;
// If count of zeros is equal to
// count of ones
if (zero == one)
{
// Store the maximum possible one
count_split = Math.max(
count_split, 1
+ maximumSplits(
arr, val,
k - Math.pow(val[i]
- val[i - 1],
2), i));
}
}
// If index is at 0, find if
// it is zero or one and
// increment the count
if (i == 0) {
arr[0] == 0 ? zero++ : one++;
// If count of zero is not equal to
// count of one, re-initialize
// count_split with 0
if (zero != one) {
count_split = 0;
}
}
// Store the returned value in dp[]
return dp[k][N] = count_split;
}
// Driver Code
let arr = [1, 0, 0, 1, 0, 1, 1, 0];
let val = [9, 7, 5, 2, 4, 12, 3, 1];
let k = 10;
let N = arr.length;
document.write(maximumSplits(arr, val, k, N))
// This code is contributed by Potta Lokesh
</script>
Producción
2
Complejidad de Tiempo : O(N*K)
Espacio Auxiliar : O(N*K)