1924 . 撿石子遊戲

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

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

User's AC Ratio

98.7% (75/76)

Submission's AC Ratio

51.2% (145/283)

Tags

TOI 2015-TOI-4th

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

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

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1 2 3
1 1000 65536 262144 1 2 3
2 1000 65536 262144 1 2 3
3 1000 65536 262144 1 2 3
4 1000 65536 262144 1 2 3
5 1000 65536 262144 2 3
6 1000 65536 262144 2 3
7 1000 65536 262144 2 3
8 1000 65536 262144 2 3
9 1000 65536 262144 2 3
10 1000 65536 262144 3
11 1000 65536 262144 3
12 1000 65536 262144 3
13 1000 65536 262144 3
14 1000 65536 262144 3
Submit
Back to Top