首页　>　文章列表　>　最大可能的平衡二进制子字符串拆分，最多花费k个

最大可能的平衡二进制子字符串拆分，最多花费k个

子字符串拆分平衡二进制
291 2023-08-29

The array in the C programming language has a fixed size, which means that once the size is specified, it cannot be changed; you can neither shrink it or extend it.

正如我们所知，数组是一组相同数据类型的元素，它们存储在连续的内存区域中。

Given an array of values v[] and a binary array a[]. The objective is to use as many k coins to divide the binary array as much as is possible while ensuring that each segment has an equal amount of 0s and 1s. i and j are the neighboring indices of the split segment, and the cost of each split is (v[i] - v[j])2.

Problem Statement

实现一个程序，找到最大可能的平衡二进制子字符串分割，最多花费k。

示例示例1

Let the Input array be: 
a: [1,0,0, 1, 0, 0, 1, 1]
The given values be: 
v: [7, 8, 9, 10, 11, 12,13,14]
K: 1

Output obtained is: 1

Explanation

由于K的值为1，我们可以在第一个和第二个索引之间进行一次切割。

在这种情况下，[0, 1] 和 [0, 0, 1, 1] 是最终结果的平衡二进制子字符串。

进行这个剪切将花费(8 - 9)^ 2 = 1，以及1 = 1。

示例示例2

Let the Input array be: 
a: [1,0 1, 0, 1, 1, 0,0]
The given values be: 
v: [2, 4, 7, 10, 11, 12, 13, 14]
K: 14

Output obtained is: 2

Explanation

The first cut will be made between the first and second index that is 4 and 7, costing us (4 - 7)^2 = 9 and the second cut will be made between the third and fourth index that is 7 and 10, costing us (7 - 10)^ 2 = 9. No more cuts are possible at this time. The balanced binary substrings in this case that would arise are [1, 0], [1, 0], and [1, 1, 0, 0].

Approach

In order to find maximum possible balanced binary substring splits with at most cost k, we take the following methodology.

Here we take a top-down approach to solve this problem and to find maximum possible balanced binary substring splits with at most cost k.

采用自顶向下的方法，或者更广为人知的动态规划方法。动态规划的主要优势是改进了简单递归的效率。动态规划可以用来优化任何包含对相同输入进行重复调用的递归解决方案。为了避免以后重新计算子问题的结果，我们的想法是将它们存储起来。通过这个简单的优化，时间复杂度从多项式降低到指数级。

Algorithm

The algorithm to find maximum possible balanced binary substring splits with at most cost K is given below.

第一步 - 开始
第二步 - 定义一个二维矩阵 m
第三步 - 定义一个函数来找到最大可能的平衡二进制子字符串分割。
Step 4 − Define integer variables zeroCount to count the number of zeros and oneCount to count the number of ones respectively
第5步 − 定义一个整数变量cntSplits来计算拆分的数量
第6步 - 遍历给定的数组 a
Step 7 − check whether the number of zeros is equal to the number of ones, then store the maximum feasible one
第8步 - 假设索引位于位置0，然后找出它是1还是0，然后增加计数
Step 9 − set the cntSplits to zero, if count of one and count of zero is unequal.
第10步 - 将结果值存储在矩阵中
Step 11 − Print the desired result obtained
Step 12 − Stop

示例：C程序

这是上述算法的C程序实现，用于找到最大可能的平衡二进制子字符串分割，最多花费k。

#include <stdio.h>
#include <limits.h>
#include <string.h>
//Define a two-dimensional matrix m
int m[1001][1001];

//Define a function to find maximum possible //balanced binary substring splits
int maxSplits(int a[], int v[], int k, int s) {
   if (k < 0) {
      return INT_MIN;
   }
   if (m[k][s] != -1) {
      return m[k][s];
   }
   
   //Define integer variables to count the number of zeros and ones 
   // Define an integer variable to count the //number of splits
   int zeroCount = 0, oneCount = 0;
   int cntSplits = 0;
   int i;
   
   //Iterating through the given array a
   for (i = s - 1; i > 0; i--) {
      a[i] == 0 ? zeroCount++ : oneCount++;
      
   // check whether the number of zeros is equal to the number of ones, then store the maximum feasible one
      if (zeroCount == oneCount) {
         cntSplits = cntSplits > (1 + maxSplits(a, v, k - (v[i] - v[i - 1]) * (v[i] - v[i - 1]), i)) ? cntSplits : (1 + maxSplits(a, v, k - (v[i] - v[i - 1]) * (v[i] - v[i - 1]), i));
      }
   }
   
   //Suppose the index is at the position 0, then find whether it is a one or a zero. then increment the count
   if (i == 0) {
      a[0] == 0 ? zeroCount++ : oneCount++;
      
   // set the cntSplits to zero , if count of one and count of zero is unequal.
      if (zeroCount != oneCount) {
         cntSplits = 0;
      }
   }
   
   // store the resultant value in the matrix
   return m[k][s] = cntSplits;
}
int main() {
   int a[] = { 1, 0, 0, 1, 0, 0, 1, 1 };
   int v[] = { 7, 8, 9, 10, 11, 12, 13, 14 };
   int k = 1;
   int s = sizeof(a) / sizeof(a[0]);
   
   //To assign a specific value to a block of memory, we use the memset() function.
   memset(m, -1, sizeof(m));
   printf("%dn", maxSplits(a, v, k, s));
   return 0;
}