Dada una string binaria S y dos enteros A , que denota el costo de invertir una substring , y B , que denota el costo de invertir todos los caracteres de una substring, la tarea es encontrar el costo mínimo para reducir la string S a 1 solo
Ejemplos:
Entrada: S = “01100”, A = 1, B = 5
Salida: 6
Explicación:
Una forma posible de hacer que todos los caracteres sean iguales a ‘1’ es la siguiente:
- Invierta la substring {S[0], S[2]}. Costo = A (= 1), La string se modifica a «11000».
- Voltee los caracteres de la substring {S[2], S[4]}. Costo de B (= 5). La string se modifica a «11111».
Por tanto, el coste total = 5+1 = 6 (que es el coste mínimo posible)
Entrada: S = “1111111”, A = 2, B = 3
Salida: 0
Enfoque: El problema dado se puede resolver con base en las siguientes observaciones:
- Suponiendo que hay P grupos disjuntos de ‘0’ continuos ,
- Si A es menor que B , entonces es óptimo convertir P grupos en un grupo ‘1’ de ‘0’ continuos realizando el primer tipo de operación por un costo de (P – 1) * A y luego convirtiendo todos los ‘ 0’ s a ‘1’ s por un costo de B.
- De lo contrario, es óptimo realizar la segunda operación en cada grupo por separado, por un costo de B * P.
Siga los pasos a continuación para resolver el problema:
- Inicialice una variable, digamos P con valor 0 para almacenar el recuento de grupos disjuntos de 0 s continuos .
- Además, inicialice una variable, digamos contar como 0 para almacenar el recuento temporal del número de 0 en un grupo.
- Itere sobre el carácter de la string S y haga lo siguiente:
- Si el carácter actual es ‘ 0 ‘ entonces incremente el conteo en 1 .
- De lo contrario, si el conteo es mayor que 0 , incremente P en 1 y luego asigne 0 al conteo .
- Si el conteo es mayor que 0 , incremente P en 1.
- Imprime el costo mínimo obtenido como (P-1)*A+B.
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 to calculate minimum cost to
// convert all the characters of S to '1'
void MinimumCost(string S, int A, int B)
{
// Stores the result
int count = 0;
// Stores the number of groups
// that have 0 as characters
int group = 0;
// Traverse the string S
for (int i = 0; i < S.size(); i++) {
// If current character is '0'
if (S[i] == '0') {
count += 1;
}
else {
// If count is greater
// than 0
if (count > 0) {
group += 1;
}
// Set the count to 0
count = 0;
}
}
// If the last few consecutive
// characters are '0'
if (count > 0)
group += 1;
// If string contains
// all characters as '1'
if (group == 0) {
cout << 0 << endl;
}
else {
// Minimum Cost
cout << min(A, B) * (group - 1) + B;
}
}
// Driver Code
int main()
{
// Given Input
int A = 1;
int B = 5;
string S = "01100";
// Function Call
MinimumCost(S, A, B);
return 0;
}
Java
// Java program for the above approach
class GFG{
// Function to calculate minimum cost to
// convert all the characters of S to '1'
static void MinimumCost(String S, int A, int B)
{
// Stores the result
int count = 0;
// Stores the number of groups
// that have 0 as characters
int group = 0;
// Traverse the string S
for(int i = 0; i < S.length(); i++)
{
// If current character is '0'
if (S.charAt(i) == '0')
{
count += 1;
}
else
{
// If count is greater
// than 0
if (count > 0)
{
group += 1;
}
// Set the count to 0
count = 0;
}
}
// If the last few consecutive
// characters are '0'
if (count > 0)
group += 1;
// If string contains
// all characters as '1'
if (group == 0)
{
System.out.println(0);
}
else
{
// Minimum Cost
System.out.print(Math.min(A, B) *
(group - 1) + B);
}
}
// Driver Code
public static void main(String args[])
{
// Given Input
int A = 1;
int B = 5;
String S = "01100";
// Function Call
MinimumCost(S, A, B);
}
}
// This code is contributed by SoumikMondal
Python3
# Python3 program for the above approach # Function to calculate minimum cost to # convert all the characters of S to '1' def MinimumCost(S, A, B): # Stores the result count = 0 # Stores the number of groups # that have 0 as characters group = 0 # Traverse the S for i in range(len(S)): # If current character is '0' if (S[i] == '0'): count += 1 else: # If count is greater # than 0 if (count > 0): group += 1 # Set the count to 0 count = 0 # If the last few consecutive # characters are '0' if (count > 0): group += 1 # If contains # all characters as '1' if (group == 0): print(0) else: # Minimum Cost print(min(A, B) * (group - 1) + B) # Driver Code if __name__ == '__main__': # Given Input A = 1 B = 5 S = "01100" # Function Call MinimumCost(S, A, B) # This code is contributed by mohit kumar 29.
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to calculate minimum cost to
// convert all the characters of S to '1'
static void MinimumCost(string S, int A, int B)
{
// Stores the result
int count = 0;
// Stores the number of groups
// that have 0 as characters
int group = 0;
// Traverse the string S
for(int i = 0; i < S.Length; i++)
{
// If current character is '0'
if (S[i] == '0')
{
count += 1;
}
else
{
// If count is greater
// than 0
if (count > 0)
{
group += 1;
}
// Set the count to 0
count = 0;
}
}
// If the last few consecutive
// characters are '0'
if (count > 0)
group += 1;
// If string contains
// all characters as '1'
if (group == 0)
{
Console.WriteLine(0);
}
else
{
// Minimum Cost
Console.Write(Math.Min(A, B) *
(group - 1) + B);
}
}
// Driver Code
public static void Main()
{
// Given Input
int A = 1;
int B = 5;
string S = "01100";
// Function Call
MinimumCost(S, A, B);
}
}
// This code is contributed by SURENDRA_GANGWAR
Javascript
<script>
// Javascript program for the above approach
// Function to calculate minimum cost to
// convert all the characters of S to '1'
function MinimumCost(S, A, B) {
// Stores the result
let count = 0;
// Stores the number of groups
// that have 0 as characters
let group = 0;
// Traverse the string S
for (let i = 0; i < S.length; i++) {
// If current character is '0'
if (S[i] == '0') {
count += 1;
}
else
{
// If count is greater
// than 0
if (count > 0) {
group += 1;
}
// Set the count to 0
count = 0;
}
}
// If the last few consecutive
// characters are '0'
if (count > 0)
group += 1;
// If string contains
// all characters as '1'
if (group == 0) {
document.write(0 + "<br>");
}
else {
// Minimum Cost
document.write(Math.min(A, B) * (group - 1) + B);
}
}
// Driver Code
// Given Input
let A = 1;
let B = 5;
let S = "01100";
// Function Call
MinimumCost(S, A, B);
// This code is contributed by gfgking.
</script>
Producción:
6
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por ujjwalgoel1103 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA