মনে করুন আমাদের একটি বাইনারি স্ট্রিং s এবং দুটি মান zero_one এবং one_zero আছে। এখন একটি অপারেশন বিবেচনা করুন যেখানে আমরা যেকোনো সাবস্ট্রিং "01" মুচতে পারি এবং zero_one পয়েন্ট পেতে পারি। অথবা আমরা যেকোনো সাবস্ট্রিং "10" মুচতে পারি এবং one_zero পয়েন্ট পেতে পারি। আমাদের যেকোনো সংখ্যক অপারেশনের পর সর্বোচ্চ পয়েন্ট খুঁজে বের করতে হবে।
উদাহরণস্বরূপ, যদি ইনপুট হয় s = "10100101", zero_one = 3, one_zero = 2, তবে আউটপুট হবে 11, কারণ আমরা "01" তিনবার মুছে 3*3 = 9 পয়েন্ট পেতে পারি। তারপর অবশিষ্ট স্ট্রিংটি 10। এটি মুছে আমরা আরও 2 পয়েন্ট পেতে পারি, তাই মোট 11।
এটি সমাধান করতে আমরা নিচের ধাপগুলো অনুসরণ করব:
A := ইনপুট স্ট্রিং দিয়ে বিটের একটি তালিকা
যদি zero_one < one_zero, তবে
zero_one এবং one_zero সোয়াপ করুন
i = 0 থেকে A-এর আকার পর্যন্ত, করুন
A[i] := A[i] XOR 1
ans := 0
stack := একটি নতুন স্ট্যাক
A-এ প্রতিটি x-এর জন্য, করুন
যদি stack খালি না থাকে এবং stack-এর শীর্ষ উপাদান < x, তবে
stack থেকে পপ করুন
ans := ans + zero_one
অন্যথায়,
x কে stack-এ পুশ করুন
ans := ans + one_zero * stack-এ 0 এবং 1-এরঘটনার ন্যূনতম
ans রিটার্ন করুন
উদাহরণ (পাইথন)
বेहतर বোঝার জন্য নিচের বাস্তবায়নটি দেখুন:
class Solution: def solve(self, S, zero_one, one_zero): A = list(map(int, S)) if zero_one < one_zero: zero_one, one_zero = one_zero, zero_one for i in range(len(A)): A[i] ^= 1 ans = 0 stack = [] for x in A: if stack and stack[-1] < x: stack.pop() ans += zero_one else: stack.append(x) ans += one_zero * min(stack.count(0), stack.count(1)) return ans ob = Solution() s = "10100101" zero_one = 3 one_zero = 2 print(ob.solve(s, zero_one, one_zero))
ইনপুট
"10100101", 3, 2
আউটপুট
11
