← 返回题目列表

AtCoder · joi2013ho4

4. JOIOI之塔

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

配点: 100 点

JOIOI塔是什么?1 这是一种由人们玩的使用磁盘的游戏。

这个游戏是 这是通过使用多个磁盘来完成的,磁盘上写有字母J,O,I 之一。这些圆盘具有不同的直径,在游戏开始时,这些圆盘按照最大直径的顺序从下到上堆叠。您想使用这些圆盘来创建尽可能多的迷你 JOIOI 塔。什么是迷你JOIOI塔? 它由 3 磁盘组成,按直径从最小到最小的顺序读取。 JOI 或 它可以读作 IOI 。但同一个盘 2 不能多次使用。

JOIOII からはミニ JOIOI の塔が <var>2</var> つ作れる

課題

写在准备好的圆盘上的字母按照长度顺序排列,从圆盘的最小直径开始。 N 字符串 它被给出为 S 。编写一个程序来查找使用这些磁盘可以制作的迷你 JOIOI 塔的最大数量。

制限

1 \leqq N \leqq 1\,000\,000  文字列 S长度

入力

从标准输入读取以下数据。

  • 第一行是一个整数 写入 N 。 表示N 是一个字符串 表示 S 的长度。
  • 第二行是一个字符串 S 。 表示

出力

表示可以创建的迷你 JOIOI 塔的最大数量的整数被发送到标准输出。 输出为 1 行。

採点基準

评分数据中,分配的分数 10 对于%,N \leqq 15 很满意。

评分数据中,分配的分数 30 对于%,N \leqq 50 很满意。

评分数据中,分配的分数 50 对于%,N \leqq 3\,000 很满意。


入力例 1

6
JOIIOI

出力例 1

2

JOIIOI 为 JOI 和 IOI 分别 1 可以创建的迷你JOIOI塔是 2 这是一个。


入力例 2

5
JOIOI

出力例 2

1

作为子序列 包含 JOI 和 IOI ,但字符 2 不能多次使用,因此不能同时取出。


入力例 3

6
JOIOII

出力例 3

2

此输入/输出示例对应于问题文本中的示例。


入力例 4

15
JJOIIOOJOJIOIIO

出力例 4

4