TopCoder

Caido
$\mathbb{W}\mathcal{aimai}\sim$

User's AC Ratio

78.3% (72/92)

Submission's AC Ratio

40.2% (140/348)

Tags

Description

有兩個煤礦區各有一群礦工在礦區採礦。因為採礦是很辛苦的工作,這些礦工需要食物讓他們保持體力。
每次一個裝載的食物到達礦區後,此礦區的礦工即可生產相同數量的煤礦。
每次裝載的食物可以是肉類裝載、魚類裝載、或麵包裝載其中的一種。

因為礦工喜歡多樣化的餐點,若能享用越多樣化的餐點,礦工的產能就越大。明確地說,礦工會考量運送到其礦區的最新裝載食物
和前兩次裝載食物(若還未有多次裝載時,則以現有次數的裝載食物為考量)來做以下的產能:

• 若考量的裝載食物只有一種類型,礦工只生產 1 單位的煤礦;

• 若考量的裝載食物內含有二種不同類型,礦工則生產 2 單位的煤礦;

• 若考量的裝載食物內含有三種不同類型,礦工則生產 3 單位的煤礦;

假設我們事先知道裝載食物的內容和運送順序,就能以裝載食物的運送順序和運送地點來影響各個礦區的產量分佈。
各個裝載食物都不能切割,必須被運送到其中一個礦區。

此兩個礦區不需要收到相同次數的裝載食物(事實上,允許將所有裝載食物運送到同一礦區)。

請寫一個程式在給定要分配到礦區之裝載食物的類型和順序的條件下,經由決定各個裝載食物應送到礦區 1 還是礦區 2 ,來幫忙
找出可以生產的最大煤礦總產量。

Input Format

第一行輸入有一個整數 N (1 ≤ N ≤ 100 000),為裝載食物的次數。
第二行輸入有一個字串含 N 個字母,依照順序為各次裝載食物的載送餐點內容。
以大寫字母'M'代表肉(meat)、'F'代表魚(fish)、或'B'代表麵包(bread)。

Output Format

請輸出一個整數,表示最大的煤礦總產量。

Sample Input 1

6
MBMFFB

Sample Output 1

12

Sample Input 2

16
MMBMBBBBMMMMMBMB

Sample Output 2

29

Hints

Problem Source

原TIOJ1344 / IOI 2007, Day 2 problemsetter: kelvin

Subtasks

No. Testdata Range Score
1 0 8
2 1 8
3 2 8
4 3 8
5 4 8
6 5 8
7 6 8
8 7 8
9 8 8
10 9 8
11 10 8
12 11 12

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 5000 65536 262144 1
1 5000 65536 262144 2
2 5000 65536 262144 3
3 5000 65536 262144 4
4 5000 65536 262144 5
5 5000 65536 262144 6
6 5000 65536 262144 7
7 5000 65536 262144 8
8 5000 65536 262144 9
9 5000 65536 262144 10
10 5000 65536 262144 11
11 5000 65536 262144 12