← 返回题目列表

AtCoder · joi2016ho_b

B. 印章拉力赛 2(收集印章 2)

中文机器翻译题面 查看原题

配点: 100 点

在JOI商业街沿大路 N 家店铺,从JOI商店街的入口到出口,每个 1, 2, \ldots, N 。 JOI商店街是单行道,只能从入口到出口。

为了振兴小镇,JOI商店街将举办盖章活动。在本次集章活动中,各店铺将 准备一张 J,O,I 印章,让在商店购物的人在印章卡上盖章。参加集章活动的人只是 3 输入一家商店。商店街入口处 3 分发五栏印章卡。1 我第一次来的商店,2 我第一次来的商店,3 从您访问过的商店获取印章。在商店街出口处领取印章卡,按照先进入的商店的印章顺序放置。 J,O,I 我们决定开展一项活动,您可以在出口处获得礼券。如果邮票的类型或顺序不同,您将不会收到礼券。

已经 N 所有商店都已决定要准备哪些邮票,但是 1 我们决定在JOI商圈开店,并决定了新店的开店地点以及店内准备的印章。开新店的地点是 i 并存储 之间 i + 1 (1 \leqq i \leqq N - 1),入口和商店 在 1 之间,存储 在 N 和退出之间做出选择。另外,新的商店印章是 从三个选项中进行选择: J,O,I 。

商圈认为越多的人可以选择领取礼券的商店,集章活动就越精彩。因此,在决定新店选址和要准备的印章时,我想找到如上所述的最多几种选择商店的方法。

課題

JOI 给定购物区现有商店准备的印章信息,编写一个程序,当您决定新商店的位置和要准备的印章时,找到选择给您礼品券的商店的最大方法。


入力

从标准输入读取以下输入。 在

  • 1 行中, 写入1 整数 给出了 N 。目前位于JOI商店街。 这意味着有 N 商店。 做。
  • 2 行中, 写入N 半角大写字母 仅由 J,O,I 组成的字符串 写入 S 。字符串 从 S 左侧开始 i 文字目 (1 \leqq i \leqq N) 是一家商店 代表 i 准备的印章类型。

出力

选择向您提供礼券的商店的最大方式数设置为标准输出。 1 行输出.

有多种方法可以选择可以接收礼券的商店。 32 请注意,它不一定落在有符号整数的范围内。


制限

所有输入数据满足以下条件。

  • 3 \leqq N \leqq 100\,000.

小課題

小課題 1 [30 点]

  • N \leqq 200 满意。

小課題 2 [20 点]

  • N \leqq 3\,000 满意。

小課題 3 [50 点]

没有其他限制。


入力例 1

5
JOIOI

出力例 1

6

入力例 1 然后,商店 1 并存储 之间 2 之间的邮票 当您开设准备 J 的新商店时,如果您将商店准备的印章从入口处按顺序排列, JJOIOI 变为。

此时,如何选择可以领取礼券的商店如下。 6 没错。 前往

  • 1, 3, 4 商店。
  • 1, 3, 6 商店。
  • 1, 5, 6 商店。
  • 2, 3, 4 商店。
  • 2, 3, 6 商店。
  • 2, 5, 6 商店。

入力例 1 如何选择可以领取礼券的商店 7 没有比这更好的了。


入力例 2

7
JJJOIII

出力例 2

18

入力例 3

4
OIIJ

出力例 3

2

入力例 3 现在,入口和商店。 1 之间的邮票 当您开设提供 J 的新商店时,选择可接收礼券的商店的方式数量将变为最多。