[AdditionalFile2343.zip](file://AdditionalFile2343.zip?type=additional_file)

P11794 [JOI 2016 Final] 集邮比赛 2 / Collecting Stamps 2

题目描述

给定一个长度为 $N$ 的仅包含字符 J、O、I 的字符串，现在你可以在该串的任意一个位置插入一个字符，求最多能有多少个子序列（不一定连续）为 JOI。

输入格式

第一行一个整数 $n$，表示长度。

第二行为一个长度为 $n$ 的字符串。

输出格式

一行，即添加后的子序列 JOI 的最大数量。

输入输出样例 #1

输入 #1

5
JOIOI

输出 #1

6

输入输出样例 #2

输入 #2

7
JJJOIII

输出 #2

18

输入输出样例 #3

输入 #3

4
OIIJ

输出 #3

2

说明/提示

【数据范围与约定】

对于所有数据，均满足 $3 \le N \le 100000$。

1. Subtask $1$（$30$ pts）：$N \le 200$。
2. Subtask $2$（$20$ pts）：$N \le 3000$。
3. Subtask $3$（$50$ pts）：无特殊限制。

#2343. 「JOI 2016 Final」邮戳拉力赛 2

标签: 传统 | 时间限制: 1000 ms | 内存限制: 256 MiB |

题目描述

本题译自 JOI 2016 Final T2「スタンプラリー 2」

至于 1 在哪儿……「スタンプラリー」这个标题曾出现在 JOI 2013/2014 春训营中，PoPoQQQ 大佬的译文戳这儿

JOI 商店街有 $N$ 家商店，这些商店从入口到出口依次编为 $1, 2, \ldots, N$ 号。商店街是单向通道，只能从入口进去，向出口走。

为了振兴小镇，小镇将要举行集邮比赛。在集邮比赛上，每家商店都会准备 $\texttt{J,O,I}$ 三种邮票中的一种，在该商店中购物的顾客即可获得一张邮票。
在比赛中，参赛选手从入口进入商业街后，需要依次进入三家商店。每位选手在入口处会得知他需要依次进入哪三家商店。保证这三家商店依次提供邮票 $\texttt{J}$，邮票 $\texttt{O}$ 和邮票 $\texttt{I}$。选手到出口时凭赛时收集的这三张邮票领取购物券。

这 $N$ 家商店已经决定了自己要准备哪种邮票。不过，在赛前，我们决定在商业街上新增一家店铺。这家店开张的地点可在店铺 $i$ 和店铺 $i+1$ $(1\leqslant i\leqslant N-1)$ 之间，或者是入口与店铺 $1$ 之间，亦或是店铺 $N$ 与出口之间。这家新建的店铺也会参赛，并准备 $\texttt{J,O,I}$ 三种邮票中的一种。

选手获得礼品券的方式越多，邮票拉力赛就越热烈。如果两名选手进入的店铺不完全相同（比如三者都不同，或是两者相同剩下一家不同），那么这两名选手获得购物劵的方式不同。
我们想通过合理安排新店铺的开张地点，使得选手获得购物券的方式尽可能多。求在理想安排下，选手最多有多少种获得购物劵的方式。

输入格式

第一行有一个整数 $N$。
第二行有一个仅由 $\texttt{J,O,I}$ 三种字符组成的字符串，字符串长度为 $N$。字符串左数第 $i$ 个字符 $(1\leqslant i\leqslant N)$ 表示商店 $i$ 提供哪种邮票。

输出格式

输出一个整数，表示在理想安排下，选手最多有多少种获得购物券的方式。
保证答案在 $\texttt{int64}$ 范围内。

样例 1

输入

5
JOIOI

输出

6

一种理想安排是新商店设置在商店 $1$ 与商店 $2$ 之间，该商店准备邮票 $\texttt{J}$ 。此时从入口走到出口，商店提供的邮票依次为 $\texttt{JJOIOI}$ 。此时，有 $6$ 种获得购物券的方式：

• 到商店 $1,3,4$；
• 到商店 $1,3,6$；
• 到商店 $1,5,6$；
• 到商店 $2,3,4$；
• 到商店 $2,3,6$；
• 到商店 $2,5,6$。

样例 2

输入

7
JJJOIII

输出

18

样例 3

输入

4
OIIJ

输出

2

新商店设置在商店街入口与商店 $1$ 之间，该商店准备邮票 $\texttt{J}$ 。

数据范围与提示

对于 $30\%$ 的数据，$N\leqslant 200$。
对于 $50\%$ 的数据，$N\leqslant 2000$。
对于所有数据，$1\leqslant N\leqslant 10^5$。