Giải bài trực tuyến

English

Vietnamese

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/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.