A. NOIOI 塔

    传统题 1000ms 256MiB

NOIOI 塔

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

样例下载

题目描述

NOIOI 塔是一种单人游戏。

这个游戏要用到一些写有 N, O, I 中任一文字的圆盘。这些圆盘的直径互不相同。游戏开始时,这些圆盘按照直径大的在下面的规则堆叠。你需要用这些圆盘做尽量多的迷你 NOIOI 塔。迷你 NOIOI 塔由 33 个圆盘构成,从直径较小的圆盘开始分别为 N, O, I 或分别为 I, O, I 。不过,每个圆盘最多只能使用一次。

给出长为 NN 的字符串 SS ,表示直径从小到大的圆盘上的文字。请编写程序求出使用这些圆盘能够做出的迷你 NOIOI 塔个数的最大值。

输入格式

第一行为一个整数 NN ,表示字符串 SS 的长度。

第二行是一个字符串 SS 。

输出格式

一行一个整数:表示能够做出的迷你 NOIOI 塔数量的最大值。

输入输出样例 #1

输入 #1

6
NOIIOI

输出 #1

2

输入输出样例 #2

输入 #2

5
NOIOI

输出 #2

1

输入输出样例 #3

输入 #3

6
NOIOII

输出 #3

2

输入输出样例 #4

输入 #4

15
NNOIIOONONIOIIO

输出 #4

4

输入输出样例解释

样例 1

NOIIOI 分别含子串 NOI 和子串 IOI 各一个,故可以做出 2 个迷你 NOIOI 塔。

样例 2

虽然 NOIOI 也分别含子串 NOI 和子串 IOI 各一个,但每个字符不能被使用两次或以上。

样例 3

对应题目描述中给出的例子。

数据范围

子任务捆绑测试。对于所有数据,1≤N≤1061\leq N \leq 10^6。

子任务 分值 N≤N\le
11 1010 N≤15N \leq 15
22 2020 N≤50N \leq 50
33 2020 N≤3000N \leq 3000
44 5050 N≤106N \leq 10^6

2026-10-13

未参加
状态
已结束
规则
OI
题目
4
开始于
2026-10-13 7:30
结束于
2026-10-13 12:00
持续时间
4.5 小时
主持人
参赛人数
16