1924 . 撿石子遊戲
TopCoder
Tags
Description
有三個人(P, E, C)走在路上很無聊，於是他們開始了一個遊戲。
他們將要走的路是一條筆直的路徑，依序有$N\leq 2\times 10^ 6$ 顆石塊排成一排。這$N$顆石塊很特別，每一顆都只能被P、E、C其中一個人撿起。之後P、E、C會在走過這條路時選一個區間開始撿石塊，將區間內所有可以被他撿起的石塊都拿起來。然而為了避免P、E、C三個人在路途中打架，他們所選定的區間兩兩交集必須要是空的。
說石持那十塊，P、E、C三個人已經走完這條路並且撿好石塊了。請計算他們三人所持有的石塊個數總和最大是多少。
Input Format
第一行有一個正整數$N\leq 2\times 10^ 6$，代表石塊的個數。
第二行包含一個有$N$個字元的字串，第$i$個字元代表能撿起第$i$顆石塊的人。
| 子任務（測資） | 額外限制 | 分數 |
| 1 (0~4) | $N\leq 20$ | 28 |
| 2 (0~9) | $N\leq 10^ 4$ | 36 |
| 3 (0~14) | 無限制 | 36 |
Output Format
請輸出一個正整數，代表三人撿起的石塊個數總和最大值。
Sample Input 1
9
PEPCPCECE
PEPCPCECE
Sample Output 1
6
Hints
以下為範例輸入中的最佳方案：
P將[PEP]中的兩個P撿起
E將[ECE]中的兩個E撿起
C將[CPC]中的兩個C撿起
Problem Source
Problem set / Description by Paupière
題目取自2015 TOI第二階段選訓第四次模擬考pB
說石持那十塊 by original description
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0~4 | 28 |
| 2 | 0~9 | 36 |
| 3 | 0~14 | 36 |