सी ++ प्रोग्राम बाइनरी स्ट्रिंग खरीदने के लिए न्यूनतम कितने सिक्कों की आवश्यकता है, यह जानने के लिए

मान लीजिए कि हमारे पास तीन नंबर c0, c1 और h हैं, और एक बाइनरी स्ट्रिंग S है। हम S में किसी भी बिट को फ्लिप कर सकते हैं। हमें प्रत्येक बदलाव के लिए h सिक्कों का भुगतान करना चाहिए। कुछ बदलावों (संभवतः शून्य) के बाद हम स्ट्रिंग खरीदना चाहते हैं। डोरी खरीदने के लिए हमें उसके सभी पात्र खरीदने चाहिए। बिट 0 खरीदने के लिए हमें c0 सिक्कों का भुगतान करना चाहिए, बिट 1 को खरीदने के लिए आपको c1 सिक्कों का भुगतान करना चाहिए। हमें स्ट्रिंग खरीदने के लिए आवश्यक सिक्कों की न्यूनतम संख्या ज्ञात करनी होगी।

तो, अगर इनपुट c0 =10 जैसा है; c1 =100; एच =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"