← 返回题目列表

AtCoder · utpc2011_3

C. iwi括号串

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

对了,我的网名是 (iwi)。 我确实以前参加过程序设计比赛。 而且,和许多朋友度过了快乐的时光。

确实,我感觉我的同伴们全都是美少女。 编程竞赛的世界,仿佛是我的后宫。 G○○gle 一定是夺走了我的后宫,毫无疑问。 为了找到昔日同伴的线索,我果然还是必须参加编程竞赛。

决定报名参加 G○○gle Code Jam。 这次的 ID,也尝试考虑使用圆括号以外的括号吧。

問題

当给定由 'i'、'w'、'('、')'、'{'、'}'、'['、']' 构成的字符串时, 想从中取出子序列,制作出线对称的字符串。 请编写程序计算最多可以制作多少字符的字符串。

给定的字符串会 至少包含一次 "iwi",而其他部分不包含 'i' 和 'w'。 更形式地说,给定的字符串是 s “iwi” t (s 与 “iwi” 以及 t 连接而成的形式表示 s 和 按字典顺序比较 t 由 '(', ')', '{', '}', '[', ']' 组成的字符串。 s 呀 请注意,它可能是 t 也可能是 0 个字符。

所构造的字符串,是从给定的字符串中抽取子序列来构造的。 子序列是指从原始字符串中取出若干字符,然后按它们在原字符串中出现的顺序连接而成。 取出的字符不必在原字符串中连续。

此外,构造的字符串也应像给定字符串一样,包含一次 “iwi” 字符串,并且其他部分不包含 'i' 和 'w'。

这里使用的水平对称的定义如下。

  1. 以下字符串水平对称。
  • 空文字列
  • “我”
  • “w” 当
  1. 文字列 x 水平对称时,后面的字符串也水平对称。
  • “我” x “我”
  • “w” 当 x “w” 当
  • "(" x ")"
  • ")" x "("
  • "{" x "}"
  • "}" x "{"
  • "[" x "]"
  • "]" x "["
  1. 只有以上项目是左右对称的。

入力

输入由 'i', 'w', '(', ')', '{', '}', '[', ']' 组成,并满足上述条件。

出力

输出可以满足上述条件所能构成的字符串的最大长度。

制約

  • 输入字符串的长度不超过15。

入出力例

入出力例 1

入力例 1:

[[[iwi[[[

输入示例 1 的输出示例:

3

只能构造出 "iwi" 这个字符串。

入出力例 2

入力例 2:

[{)iwi(]}

输入示例 2 的输出示例:

7

可以构造出 "[)iwi(]" 或 "{)iwi(}" 等7个字符的字符串。