Problem : 45 - Miners

Problem Statistics

Solved Member: 37　　Submission: 102　　User Tried: 37

Statement:

有兩個煤礦區各有一群礦工在礦區採礦。因為採礦是很辛苦的工作，這些礦工需要食物讓他們保持體力。每次一個裝載的食物到達礦區後，此礦區的礦工即可生產相同數量的煤礦。每次裝載的食物可以是肉類裝載、魚類裝載、或麵包裝載其中的一種。
因為礦工喜歡多樣化的餐點，若能享用越多樣化的餐點，礦工的產能就越大。明確地說，礦工會考量運送到其礦區的最新裝載食物和前兩次裝載食物(若還未有多次裝載時，則以現有次數的裝載食物為考量)來做以下的產能：

•若考量的裝載食物只有一種類型，礦工只生產1單位的煤礦；
•若考量的裝載食物內含有二種不同類型，礦工則生產2單位的煤礦；
•若考量的裝載食物內含有三種不同類型，礦工則生產3單位的煤礦；

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

此兩個礦區不需要收到相同次數的裝載食物(事實上，允許將所有裝載食物運送到同一礦區)。

Task:

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

Input:Output:

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

佔總分40分的測試資料中，裝載食物的次數N最大為20。

請輸出一個整數，表示最大的煤礦總產量。

Sample Input:Sample Output:

SAMPLE 1:
6
MBMFFB

SAMPLE 2:
16
MMBMBBBBMMMMMBMB

SAMPLE 1:
12

SAMPLE 2:
29

HINT:

在左側範例中，最大的煤礦產量的裝載食物的分佈為依以下順序：礦區1、礦區1、礦區2、礦區2、礦區1、礦區2。裝載食物所導致的煤礦產量依序為1、2、1、2、3、3單位的煤礦，其最大的煤礦總產量為12單位的煤礦。注意，有多種分佈方式可達到此最大的煤礦總產量。

Source:

IOI 2007

Problem Setter

Nekosyndrome

Testdata:

Test	Time	Memory	Score
0-1	2000ms	65536kb
0-2	2000ms	65536kb
1	2000ms	65536kb	8
2	2000ms	65536kb	8
3	2000ms	65536kb	8
4	2000ms	65536kb	8
5	2000ms	65536kb	8
6	2000ms	65536kb	8
7	2000ms	65536kb	8
8	2000ms	65536kb	8
9	2000ms	65536kb	9
10	2000ms	65536kb	9
11	2000ms	65536kb	9
12	2000ms	65536kb	9