สมมติว่าเรามีตัวเลขสามตัว c0, c1 และ h และสตริงไบนารี S เราสามารถพลิกบิตใดๆ ใน S ได้ เราควรจ่าย h เหรียญสำหรับการเปลี่ยนแปลงแต่ละครั้ง หลังจากการเปลี่ยนแปลงบางอย่าง (อาจเป็นศูนย์) เราต้องการซื้อสตริง ในการซื้อสายอักขระ เราควรซื้ออักขระทั้งหมด ในการซื้อบิต 0 เราควรจ่ายเหรียญ c0 เพื่อซื้อบิต 1 คุณควรจ่ายเหรียญ c1 เราต้องหาจำนวนเหรียญขั้นต่ำที่จำเป็นในการซื้อสตริง
ดังนั้นหากอินพุตเป็นเหมือน c0 =10; c1 =100; ชั่วโมง =1; S ="01010" จากนั้นผลลัพธ์จะเป็น 52 เพราะก่อนอื่นเราจะเปลี่ยนบิตที่ 2 และ 4 ใน 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
