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 xu cho mỗi lần thay đổi. Sau một số thay đổi (có thể không) chúng ta muốn mua chuỗi đó. Để mua chuỗi, chúng ta phải mua tất cả các ký tự của nó. Để mua bit 0 ta phải trả c0 đồng xu, để mua bit 1 ta phải trả c1 đồng xu. Chúng ta phải tìm số đồng xu tối thiểu cần để mua chuỗi.
Ví dụ, nếu đầu vào là c0 = 10; c1 = 100; h = 1; S = "01010", thì đầu ra sẽ là 52, vì đầu tiên ta thay đổi bit thứ 2 và 4 trong S và trả 2 đồng xu cho việc đó. Bây giờ chuỗi sẽ là 00000. Sau đó, ta có thể mua chuỗi và trả 5·10=50 đồng xu cho đó. Tổng số đồng xu trả sẽ là 2+50=52.
Các bước
Để giải quyết bài toán này, chúng ta sẽ làm theo các bước sau:
k := 0 n := kích thước của S for khởi tạo i := 0, khi i < n, cập nhật (tăng i lên 1), do: if S[i] giống '0', thì: k := k + minimum của c0 và (c1 + h) Ngược lại k := k + minimum của (c0 + h) và c1 return k
Ví dụ
Xem 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