バイナリ文字列を購入するために必要なコインの最小数を見つけるためのC++プログラム

3つの数値c0、c1、hがあり、2進数の文字列Sがあるとします。Sの任意のビットを反転できます。変更ごとにhコインを支払う必要があります。いくつかの変更（おそらくゼロ）の後、文字列を購入したいと思います。文字列を購入するには、そのすべての文字を購入する必要があります。ビット0を購入するには、c0コインを支払う必要があり、ビット1を購入するには、c1コインを支払う必要があります。ストリングを購入するために必要なコインの最小数を見つける必要があります。

したがって、入力がc0=10のような場合。 c1 =100; h =1; S ="01010"の場合、出力は52になります。これは、最初にSの2番目と4番目のビットを変更し、そのために2コインを支払うためです。これで弦は00000になります。その後、弦を購入して5⋅10=50コインを支払うことができます。支払われるコインの総数は2+50=52になります。

ステップ

これを解決するには、次の手順に従います-

k := 0
n := size of S
for initialize i := 0, when i < n, update (increase i by 1), do:
   if S[i] is same as '0', then:
      k := k + minimum of c0 and (c1 + h)
   Otherwise
      k := k + minimum of (c0 + h) and c1
return k

例

理解を深めるために、次の実装を見てみましょう-

#include <bits/stdc++.h>
using namespace std;

int solve(int c0, int c1, int h, string S) {
   int k = 0;
   int n = S.size();
   for (int i = 0; i < n; i++) {
      if (S[i] == '0')
         k = k + min(c0, c1 + h);
      else
         k = k + min(c0 + h, c1);
   }
   return k;
}
int main() {
   int c0 = 10;
   int c1 = 100;
   int h = 1;
   string S = "01010";
   cout << solve(c0, c1, h, S) << endl;
}

入力

10, 100, 1, "01010"

出力

52