A7220 | $雾港学宫的括号匹配$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

雾港学宫的封印符文是一串括号。由于年代久远，符文顺序被打乱，你只能通过“删掉一些字符”来恢复它的稳定结构。 给定一个只包含 (和) 的字符串 $s$，你可以删除任意多个字符（也可以把整个串删空）。删除后剩下的字符保持原有相对顺序。 我们称一个括号串是 合法括号串 （也叫正确括号序列），当且仅当它能被完全配对，例如：空串、 ()() 、 (()) 都是合法的。 请你求出：最少需要删除多少个字符，才能使剩下的字符串变成合法括号串。 ---

第一行一个整数 $n$，表示字符串长度。 第二行一个长度为 $n$ 的字符串 $s$，只包含字符 (和) 。

输出一个整数，表示最少删除次数。

输入 #1

8
())(()))

输出 #1

样例解释 解释：删掉第 $3$ 个字符 ) 和第 $8$ 个字符 )，剩下 ()(()) 是合法括号串，所以答案为 $2$，并且无法做到 $1$。 数据范围与测试点 测试点分层 ： 测试点编号$n$ 上界$1\sim4$$n\le20$$5\sim10$$n\le10000$$11\sim20$$n\le200000$

C++ 编辑器

输入

输出