C++ 最大可能的平衡二进制子字符串拆分的最大成本为k

C编程语言中的数组有固定的大小，这意味着一旦指定了大小，就无法更改；你既不能缩小它也不能扩展它。

我们知道，数组是一组具有相同数据类型的元素，保存在连续的内存区域中。

给定一个值数组v[]和一个二进制数组a[]。目标是使用尽可能多的k个硬币来尽可能多地分割二进制数组，同时确保每个段都有相等数量的0和1。i和j是分割段的相邻索引，每个分割的成本为(v[i]-v[j])2。

问题陈述

实现一个程序，找到最大可能的平衡二进制子字符串拆分的最大成本为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

获得的输出为：1

解释

由于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

解释

第一次切割将在第一个和第二个索引之间进行，即4和7，成本是(4 – 7)^2 = 9。第二次切割将在第三个和第四个索引之间进行，即7和10，成本是(7 – 10)^2 = 9。此时无法进行更多的切割。在这种情况下，可能出现的平衡的二进制子串是[1, 0]，[1, 0]和[1, 1, 0, 0]。

方法

为了找到最大可能的在成本最多为k的情况下平衡的二进制子串的分割，我们采用以下方法。

在这里，我们采用自顶向下的方法来解决这个问题，以及找到最大可能的在成本最多为k的情况下平衡的二进制子串的分割。

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

步骤

以下是找到最大可能的在成本最多为K的情况下平衡的二进制子串的分割的算法。

步骤1 - 开始
步骤2 - 定义一个二维矩阵m
步骤3 - 定义一个函数来找到最大可能的平衡的二进制子串的分割
步骤4 - 定义整数变量zeroCount来计算0的数量，以及oneCount来计算1的数量
步骤5 - 定义整数变量cntSplits来计算分割的数量
步骤6 - 迭代给定的数组a
步骤7 - 检查0的数量是否等于1的数量，然后存储最大可行的结果
步骤8 - 假设索引在位置0上，然后找出它是1还是0，并增加计数
步骤9 - 如果1的计数和0的计数不相等，则将cntSplits设为0
步骤10 - 将结果值存储在矩阵中
步骤11 - 打印所得到的期望结果
步骤12 - 停止

示例：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("%d\n", maxSplits(a, v, k, s));
   return 0;
}