Mô tả
Trung tâm điều hành sân bay Tân Sơn Nhất đang nâng cấp hệ thống bảng điện tử hiển thị vị trí cổng lên máy bay. Thay vì dùng màn hình LCD, đội ngũ kỹ sư quyết định dùng hệ thống mảng điểm (dot-matrix) với các bóng đèn LED để tăng độ bền và khả năng nhìn rõ từ xa.
Mỗi cổng được gán một mã nhị phân duy nhất để tối ưu hóa việc truyền tải tín hiệu. Bảng LED được chia thành k cột, mỗi cột chỉ có thể hiển thị một bóng đèn sáng (bit 1) hoặc tắt (bit 0). Hệ thống có thể thiết lập trạng thái cho toàn bộ k cột cùng lúc với chi phí 1 đơn vị điện năng.
Tuy nhiên, sau mỗi lần thiết lập, hệ thống có thể chọn giữ nguyên trạng thái của một số cột liên tiếp và chỉ cập nhật các cột bên ngoài khoảng đó. Cụ thể, nếu ta chọn giữ nguyên từ cột L đến cột R, thì hệ thống chỉ tốn chi phí thiết lập cho các cột từ 1 đến L-1 và từ R+1 đến k. Các cột từ L đến R giữ nguyên giá trị cũ.
Bài toán: Cho một chuỗi bit mục tiêu độ dài k, và một cấu hình ban đầu của bảng LED (tất cả các bit đều là 0). Hãy tính số đơn vị điện năng nhỏ nhất cần thiết để biến đổi bảng LED từ trạng thái toàn 0 thành đúng chuỗi bit mục tiêu.
Đầu vào
Một chuỗi nhị phân s chỉ gồm các ký tự '0' và '1' (độ dài từ 1 đến 1000).
Đầu ra
Một số nguyên duy nhất là số đơn vị điện năng nhỏ nhất.
Ràng buộc
- Độ dài chuỗi s nằm trong khoảng từ 1 đến 1000.
Ví dụ
Ví dụ 1:
- Đầu vào:
010 - Đầu ra:
1 - Giải thích: Đếm số cụm bit '1' liên tiếp trong chuỗi. Chuỗi
010chỉ có đúng 1 cụm '1' (ký tự ở vị trí 2), nên chỉ cần 1 lần bật đèn cho cụm đó, các cột còn lại giữ nguyên trạng thái 0 ban đầu. Đáp án: 1.
Ví dụ 2: