Giả sử chúng ta có ba số c0, c1 và h, và một chuỗi nhị phân S. Chúng ta có thể lật bất kỳ bit nào trong S. Chúng ta phải trả h đồng cho mỗi lần thay đổi. Sau một số thay đổi (có thể bằng không), chúng tôi muốn mua chuỗi. Để mua chuỗi chúng ta nên mua tất cả các ký tự của nó. Để mua bit 0, chúng ta nên trả c0 xu, để mua bit 1, bạn phải trả c1 xu. Chúng tôi phải tìm số xu tối thiểu cần thiết để mua chuỗi.
Vì vậy, nếu đầu vào giống như c0 =10; c1 =100; h =1; S ="01010", thì đầu ra sẽ là 52, bởi vì trước hết chúng ta thay đổi bit thứ 2 và thứ 4 trong S và trả 2 đồng tiền cho điều đó. Bây giờ chuỗi sẽ là 00000. Sau đó, chúng ta có thể mua chuỗi và trả 5⋅10 =50 xu cho điều đó. Tổng số xu được thanh toán sẽ là 2 + 50 =52.
Các bước
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
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
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
#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;
} Đầu vào
10, 100, 1, "01010"
Đầu ra
52