Оптимально разместить нули и единицы из двоичной строки в K сегментов

Опубликовано: 7 Января, 2022

Дана двоичная строка S , состоящая из нулей и единиц. Вы должны разместить 0 и 1 в K сегментов таким образом, чтобы выполнялись следующие условия:

  1. Вы заполняете ведра нулями и единицей, сохраняя относительный порядок нулей и единиц. Например, вы не можете поместить S [1] в сегмент 2 и S [0] в сегмент 1. Вы должны сохранить исходный порядок двоичной строки.
  2. Ни одно ведро не должно оставаться пустым, и ни один элемент в строке не должен оставаться неаккомодированным.
  3. Сумма всех произведений (количество нулей * количество единиц) для каждого ведра должна быть минимальной среди всех возможных вариантов размещения.

Если решение невозможно, выведите -1.

Примеры:

 Ввод: S = "0001", K = 2
Выход: 0
У нас есть 3 варианта: {"0", "001"}, {"00", "01"}, {"000", 1}
При первом выборе мы получим 1 * 0 + 2 * 1 = 2
Второй вариант, мы получим 2 * 0 + 1 * 1 = 1
Третий вариант, мы получим 3 * 0 + 0 * 1 = 0
Из всех трех вариантов третий вариант 
дает минимальный ответ.

Ввод: S = "0101", K = 1
Выход: 1
Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Рекурсивная реализация: вы должны разместить двоичную строку в K сегментов, не нарушая вышеуказанных условий. Затем можно сделать простое рекурсивное решение, сначала заполнив i-е ведро (начиная с 0), поместив элементы от начала до N (N = длина двоичной строки) и продолжая добавлять счетные нули и единицы до начального индекса. Для каждой итерации, если до начала осталось x нулей и y единиц, то повторяется для f (start, K) = x * y + f (start + 1, K - 1), потому что следующее размещение будет выполнено с (start + 1) - -й индекс и оставшиеся сегменты будут K - 1.

Итак, рекурсивная формула будет -

F(start, current_bucket) =  |           |
                            |       min |  F(i + 1, next_bucket) + (ones * zeroes in current_bucket)  
                            |           |   
                            | i = start to N

Нисходящий динамический подход:
Рекурсивное отношение можно изменить на динамическое решение , сохранив результаты различных комбинаций переменной start и bucket в двумерном массиве DP. Мы можем использовать тот факт, что порядок строки должен быть сохранен. Вы можете иметь двумерный массив, сохраняющий состояния размера [размер строки * ведра] , где dp [i] [j] сообщит нам минимальное значение размещения до i-го индекса строки с использованием j + 1 ведер. Наш окончательный ответ будет в dp [N-1] [K-1] .

Below is the implementation of the above approach:  

C++

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// 2-D dp array saving different states
// dp[i][j] = minimum value of accommodation
// till i"th index of the string
// using j+1 number of buckets.
vector<vector<int> > dp;
 
// Function to find the minimum required
// sum using dynamic programming
int solveUtil(int start, int bucket, string str, int K)
{
    int N = str.size();
 
    // If both start and bucket reached end then
    // return 0 else that arrangement is not possible
    // so return INT_MAX
    if (start == N) {
        if (bucket == K)
            return 0;
        return INT_MAX;
    }
 
    // Corner case
    if (bucket == K)
        return INT_MAX;
 
    // If state if already calculated
    // then return its answer
    if (dp[start][bucket] != -1)
        return dp[start][bucket];
 
    int zeroes = 0;
    int ones = 0;
    int ans = INT_MAX;
 
    // Start filling zeroes and ones which to be accommodated
    // in jth bucket then ans for current arrangement will be
    // ones*zeroes + recur(i+1, buket+1)
    for (int i = start; i < N; ++i) {
        if (str[i] == "1")
            ones++;
        else
            zeroes++;
 
        if (ones * zeroes > ans)
            break;
 
        int temp = solveUtil(i + 1, bucket + 1, str, K);
 
        // If this arrangement is not possible then
        // don"t calculate further
        if (temp != INT_MAX) {
            ans = min(ans, temp + (ones * zeroes));
        }
    }
 
    return dp[start][bucket] = ans;
}
 
// Function to initialze the dp and call
// solveUtil() method to get the answer
int solve(string str, int K)
{
    int N = str.size();
    dp.clear();
    dp.resize(N, vector<int>(K, -1));
 
    // Start with 0-th index and 1 bucket
    int ans = solveUtil(0, 0, str, K);
 
    return ans == INT_MAX ? -1 : ans;
}
 
// Driver code
int main()
{
    string S = "0101";
 
    // K buckets
    int K = 2;
 
    cout << solve(S, K) << endl;
 
    return 0;
}

Java

// Java implementation of the approach
import java.io.*;
import java.util.*;
 
class GFG{
 
// 2-D dp array saving different states
// dp[i][j] = minimum value of accommodation
// till i"th index of the string
// using j+1 number of buckets.
static int[][] dp;
 
// Function to find the minimum required
// sum using dynamic programming
static int solveUtil(int start, int bucket,
                     String str, int K)
{
    int N = str.length();
     
    // If both start and bucket reached end
    // then return 0 else that arrangement
    // is not possible so return INT_MAX
    if (start == N)
    {
        if (bucket == K)
        {
            return 0;
        }
        return Integer.MAX_VALUE;
    }
     
    // Corner case
    if (bucket == K)
    {
        return Integer.MAX_VALUE;
    }
     
    // If state if already calculated
    // then return its answer
    if (dp[start][bucket] != -1)
    {
        return dp[start][bucket];
    }
    int zeroes = 0;
    int ones = 0;
    int ans = Integer.MAX_VALUE;
     
    // Start filling zeroes and ones which to be
    // accommodated in jth bucket then ans for
    // current arrangement will be
    // ones*zeroes + recur(i+1, buket+1)
    for(int i = start; i < N; ++i)
    {
        if (str.charAt(i) == "1")
        {
            ones++;
        }
        else
        {
            zeroes++;
        }
        if (ones * zeroes > ans)
        {
            break;
        }
        int temp = solveUtil(i + 1, bucket + 1, str, K);
         
        // If this arrangement is not possible then
        // don"t calculate further
        if (temp != Integer.MAX_VALUE)
        {
            ans = Math.min(ans, temp + (ones * zeroes));
        }
    }
    return dp[start][bucket] = ans;
}
 
// Function to initialze the dp and call
// solveUtil() method to get the answer
static int solve(String str, int K)
{
    int N = str.length();
    dp = new int[N][K];
     
    for(int[] row : dp)
    {
        Arrays.fill(row, -1);
    }
     
    // Start with 0-th index and 1 bucket
    int ans = solveUtil(0, 0, str, K);
    return ans == Integer.MAX_VALUE ? -1 : ans;
}
 
// Driver code
public static void main(String[] args)
{
    String S = "0101";
     
    // K buckets
    int K = 2;
     
    System.out.println(solve(S, K));
}
}
 
// This code is contributed by rag2127

Python3

# Python3 implementation of the approach
 
# 2-D dp array saving different states
# dp[i][j] = minimum value of accommodation
# till i"th index of the str1ing
# using j+1 number of buckets.
 
# Function to find the minimum required
# sum using dynamic programming
def solveUtil(start, bucket, str1, K,dp):
 
    N = len(str1)
 
    # If both start and bucket reached end then
    # return 0 else that arrangement is not possible
    # so return INT_MAX
    if (start == N) :
        if (bucket == K):
            return 0
        return 10**9
 
 
    # Corner case
    if (bucket == K):
        return 10**9
 
    # If state if already calculated
    # then return its answer
    if (dp[start][bucket] != -1):
        return dp[start][bucket]
 
    zeroes = 0
    ones = 0
    ans = 10**9
 
    # Start filling zeroes and ones which to be accommodated
    # in jth bucket then ans for current arrangement will be
    # ones*zeroes + recur(i+1, buket+1)
    for i in range(start,N):
        if (str1[i] == "1"):
            ones += 1
        else:
            zeroes += 1
 
        if (ones * zeroes > ans):
            break
 
        temp = solveUtil(i + 1, bucket + 1, str1, K,dp)
 
        # If this arrangement is not possible then
        # don"t calculate further
        if (temp != 10**9):
            ans = min(ans, temp + (ones * zeroes))
 
    dp[start][bucket] = ans
 
    return ans
 
 
# Function to initialze the dp and call
# solveUtil() method to get the answer
def solve(str1, K):
 
    N = len(str1)
 
    dp = [[-1 for i in range(K)] for i in range(N)]
 
    # Start with 0-th index and 1 bucket
    ans = solveUtil(0, 0, str1, K,dp)
 
    if ans == 10**9:
        return -1
    else:
        return ans
 
 
# Driver code
 
s = "0101"
S=[i for i in s]
 
# K buckets
K = 2
 
print(solve(S, K))
 
# This code is contributed by mohit kumar 29

C#

// C# implementation of the approach
using System;
class GFG
{
     
    // 2-D dp array saving different states
    // dp[i][j] = minimum value of accommodation
    // till i"th index of the string
    // using j+1 number of buckets.
    static int[,] dp;
      
    // Function to find the minimum required
    // sum using dynamic programming
    static int solveUtil(int start, int bucket,
                         string str, int K)
    {
        int N = str.Length;
          
        // If both start and bucket reached end
        // then return 0 else that arrangement
        // is not possible so return INT_MAX
        if (start == N)
        {
            if (bucket == K)
            {
                return 0;
            }
            return Int32.MaxValue;
        }
          
        // Corner case
        if (bucket == K)
        {
            return Int32.MaxValue;
        }
          
        // If state if already calculated
        // then return its answer
        if (dp[start,bucket] != -1)
        {
            return dp[start, bucket];
        }
        int zeroes = 0;
        int ones = 0;
        int ans = Int32.MaxValue;
          
        // Start filling zeroes and ones which to be
        // accommodated in jth bucket then ans for
        // current arrangement will be
        // ones*zeroes + recur(i+1, buket+1)
        for(int i = start; i < N; ++i)
        {
            if (str[i] == "1")
            {
                ones++;
            }
            else
            {
                zeroes++;
            }
            if (ones * zeroes > ans)
            {
                break;
            }
            int temp = solveUtil(i + 1, bucket + 1, str, K);
              
            // If this arrangement is not possible then
            // don"t calculate further
            if (temp != Int32.MaxValue)
            {
                ans = Math.Min(ans, temp + (ones * zeroes));
            }
        }
        return dp[start, bucket] = ans;
    }
      
    // Function to initialze the dp and call
    // solveUtil() method to get the answer
    static int solve(string str, int K)
    {
        int N = str.Length;
        dp = new int[N, K];       
        for(int i = 0; i < N; i++)
        {
            for(int j = 0; j < K; j++)
            {
       
C++ Олимпиады по программированию

РЕКОМЕНДУЕМЫЕ СТАТЬИ

С++ Std против Stl
20 Февраля, 2023
C++ функция __builtin_popcount()
20 Февраля, 2023
Как получить доступ к элементам в наборе по индексу в С++?
20 Февраля, 2023
Строка С++ для плавающей/двойной и наоборот
20 Февраля, 2023
Преобразование шестнадцатеричной строки в целое число со знаком в С++
20 Февраля, 2023
C++ функция getenv()
20 Февраля, 2023
Вложенный, если в C++
20 Февраля, 2023
C++ вектор структур
20 Февраля, 2023