|
|
Từ tập các bài có trên SPOJ (oi)
2255. IOI07 Miners
Mã bài: NKMINERS
|
Có hai mỏ than, mỗi mỏ có một nhóm thợ mỏ làm việc. Khai thác than là công việc vất vả, do ðó các thợ mỏ cần thực phẩm ðể hoạt ðộng. Mỗi khi một ðợt vận chuyển thực phẩm ðến mỏ, các thợ mỏ sẽ khai thác ðược một lượng than nào ðó. Có 3 loại thực phẩm ðược vận chuyển: thịt, cá và bánh mì.
Các thợ mỏ muốn thực ðơn ða dạng. Họ sẽ làm việc với nãng suất cao hơn nếu ðược cung cấp nguồn thực phẩm ða dạng. Chính xác hơn, mỗi khi một ðợt vận chuyển ðến mỏ, họ sẽ so sánh ðợt vận chuyển này với hai ðợt vận chuyển liền trước (hoặc ít hơn nếu chưa ðủ):
- Nếu các ðợt vận chuyển cùng một loại thực phẩm, họ sẽ sản xuất ðược 1 ðơn vị than.
- Nếu có 2 loại thực phẩm khác nhau trong các ðợt vận chuyển, họ sẽ sản xuất ðược 2 ðơn vị than.
- Nếu có 3 loại thực phẩm khác nhau trong các ðợt vận chuyển, họ sẽ sản xuất ðược 3 ðơn vị than.
Biết trước các loại thực phẩm và thứ tự chúng ðược vận chuyển, ta có thể tác ðộng lên lượng than sản xuất ðược bằng cách chỉ ðịnh ðợt vận chuyển nào sẽ ðến mỏ than nào.
Các ðợt vận chuyển không thể ðược chia nhỏ, lượng thực phẩm của mỗi ðợt phải ðược gửi toàn bộ ðến một trong hai mỏ.
Hai mỏ than không nhất thiết phải nhận số ðợt vận chuyển như nhau (thậm chí có thể gửi tất cả các ðợt vận chuyển ðến một mỏ).
Biết các loại thực phẩm theo thứ tự chúng ðược vận chuyển, hãy tìm tổng lượng than lớn nhất có thể sản xuất (trong cả hai mỏ) bằng cách quyết ðịnh ðợt vận chuyển nào sẽ ðược gửi ðến mỏ 1, ðợt vận chuyển nào sẽ ðược gửi ðến mỏ 2.
Dữ liệu
- Dòng ðầu tiên chứa 1 số nguyên dương N (1 ≤ N ≤ 100000), số ðợt vận chuyển thực phẩm.
- Dòng thứ hai chứa một chuỗi gồm N ký tự, cho biết các loại thực phẩm theo thứ tự chúng ðược phân phối. Mỗi ký tự sẽ có dạng một trong 3 chữ cái in hoa: 'M' (thịt), 'F' (cá) hoặc 'B' (bánh mì).
Kết qủa
In ra một số nguyên duy nhất, là tổng lượng than lớn nhất có thể sản xuất ðược.
Ví dụ
Dữ liệu:
6
MBMFFB
Kết qủa
12
Dữ liệu:
16
MMBMBBBBMMMMMBMB
Kết qủa
29
Trong ví dụ ðầu tiên, bằng cách phân phối các chuyến hàng theo thứ tự: mỏ 1, mỏ 1, mỏ 2, mỏ 2, mỏ 1, mỏ 2, lượng than sản xuất ðược sẽ lần lượt là 1, 2, 1, 2, 3, 3. Tổng lượng than là 12 ðơn vị. Có thể phân phối theo cách khác ðể ðạt ðược tổng lượng than này.
| Được gửi lên bởi: | Ngô Minh Ðức |
| Ngày: | 2007-12-28 |
| Thời gian chạy: | 1s-2s |
| Giới hạn mã nguồn: | 50000B |
| Ngôn ngữ cho phép: | Tất cả ngoại trừ: AWK CLOJ ERL F# GO JS PERL 6 PYTH 3.1.2 SCALA SED TCL |
| Nguồn bài: | IOI 2007 - Croatia |
|
|
|
|
