2756: C. 博物馆
题目描述
某博物馆想举办一个集章打卡活动。
在博物馆中，有 n 个展厅，编号依次为 1 , 2 … n 。每个展厅都可以盖一种纪念章。
博物馆设计了三种纪念章，分别为 1 号， 2 号， 3 号三种章。每个展厅的盖章类型是已知的，集齐三种 章就可以获得一份博物馆纪念品。
盖章时遵循以下规则：
每种章只能盖一次；
1 号章没有要求；（ 1号章必须第一个盖）
2 号章必须要在 1 号章盖完之后才能盖；
3 号章必须要在 2 号章盖完之后才能盖；
参加活动的游客只能按照展厅的编号大小 1 , 2 … n 依次游览，他需要从中选择三个展厅，集齐三种章。
为了让游客有更多可能集齐三种章，博物馆想为这次活动特地增设一个展厅。
请你计算出，增设一个展厅后，最多有多少种集齐三种章的方案？
增设展厅的盖章种类没有限制，新增展厅可以放在现有的两个相邻展厅之间，也可以放在最开始（1号展 厅前）或者最后（ n号展厅后）。
输入
第一行有一个整数 n 。
第二行有一个仅由 1 , 2 ，3 三种字符组成的字符串，字符串长度为 n ，依次表示 n 个展厅的章；
1 , 2 ，3 分别表示 1 号章、 2 号章、 3 号章。
输出
样例输入 复制
5
12323样例输出 复制
6提示
样例 #2
样例输入 #2
样例输出 #2
|
18 |
样例解释 #2
可以在第 3 个和第 4 个展厅之间增加一个 2 号章的展厅。
样例解释 #3
可以在第 1 个展厅之前增加一个 1 号章展厅。
数据范围与提示:
对于 30% 的数据，n ≤ 200。
对于 50% 的数据， n ≤ 2000。
对于所有的数据，1≤ n ≤ 105。