ধরুন আমাদের তিনটি সংখ্যা c0, c1 এবং h, এবং একটি বাইনারি স্ট্রিং 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
