मान लीजिए हमारे पास तीन संख्याएं c0, c1 और h हैं, और एक बाइनरी स्ट्रिंग S। हम S में किसी भी बिट को फ्लिप कर सकते हैं। हमें प्रत्येक बदलाव के लिए h सिक्कों का भुगतान करना चाहिए। कुछ बदलावों (संभवतः शून्य) के बाद हम स्ट्रिंग खरीदना चाहते हैं। स्ट्रिंग खरीदने के लिए हमें इसके सभी वर्ण खरीदने चाहिए। बिट 0 खरीदने के लिए हमें c0 सिक्कों का भुगतान करना चाहिए, बिट 1 खरीदने के लिए आपको c1 सिक्कों का भुगतान करना चाहिए। हमें स्ट्रिंग खरीदने के लिए आवश्यक सिक्कों की न्यूनतम संख्या ढूंढनी है।
उदाहरण के लिए, यदि इनपुट c0 = 10; c1 = 100; h = 1; S = "01010" है, तो आउटपुट 52 होगा, क्योंकि पहले हम S में दूसरे और चौथे बिट को बदलते हैं और उसके लिए 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
