最大可能的平衡二進位子字串拆分，最多花費k個-C++-PHP中文網

最大可能的平衡二進位子字串拆分，最多花費k個

WBOY

發布： 2023-08-29 09:41:07

轉載

1214 人瀏覽過

最大可能的平衡二進位子字串拆分，最多花費k個

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

登入後複製