สมมติว่าเรามีตัวเลข 3 ตัว c0, c1 และ h และสตริงไบนารี S เราสามารถพลิกบิตใน S ใดๆ ได้ ต้องจ่าย h เหรียญต่อการเปลี่ยนแปลง หลังจากเปลี่ยนแปลงบางอย่าง (อาจเป็นศูนย์) เราต้องการซื้อสตริงนี้ เพื่อซื้อสตริง ต้องซื้อทุกตัวอักษรในมัน เพื่อซื้อบิต 0 ต้องจ่าย c0 เหรียญ ซื้อบิต 1 จ่าย c1 เหรียญ เราต้องหาจำนวนเหรียญขั้นต่ำที่ต้องจ่ายเพื่อซื้อสตริง
เช่น ถ้าค่าที่ป้อนเข้าเป็น c0 = 10; c1 = 100; h = 1; S = "01010" ผลลัพธ์จะได้ 52 เพราะก่อนอื่นเราเปลี่ยนบิตที่ 2 และ 4 ใน S จ่าย 2 เหรียญ ตอนนี้สตริงจะเป็น 00000 หลังจากนั้นซื้อสตริงจ่าย 5*10=50 เหรียญ รวมเหรียญที่จ่าย 2+50=52
ขั้นตอนการแก้ปัญหา
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนดังนี้:
k := 0 n := ขนาดของ S สำหรับ i := 0 เมื่อ i < n เพิ่ม i ทีละ 1 ทำ: ถ้า S[i] เท่ากับ '0' แล้ว: k := k + min(c0, c1 + h) มิฉะนั้น k := k + min(c0 + h, c1) คืนค่า 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
