大样例在题库第3587题下载

括号序列 (bracket)

题目描述

括号序列是一种特殊的字符串，只由 ( 和 ) 组成。 合法括号序列定义：

1. 空串是合法括号序列。
2. 若 $A$ 和 $B$ 均是合法括号序列，则 $A$ 和 $B$ 连接而成的括号序列是合法括号序列。
3. 若 $A$ 是合法括号序列，则 $(A)$ 是合法括号序列。

套娃序列定义：如果一个长为 $2m$ 的合法括号序列满足前 $m$ 个字符是 (，后 $m$ 个字符是 )，那么这个括号序列是一个套娃序列。特殊地，空串是套娃序列。

给定括号序列 $s$，请你删除 $s$ 的一个合法括号子序列（子序列不需要连续），使得剩下的部分是一个套娃序列。在此前提下，请最小化剩余串的长度。 请求出剩余串的最小长度；无解请输出 $-1$。

输入格式

在文件 bracket.in 中输入。

一行一个仅由 ( 和 ) 构成的括号序列 $s$。

输出格式

在文件 bracket.out 中输出。

输出一行一个整数，表示剩余串的最小长度，无解输出 $-1$。

样例

样例输入 #1

(())

样例输出 #1

0

样例输入 #2

(()())

样例输出 #2

2

样例输入 #3

(

样例输出 #3

-1

###样例2说明

题解里隐含的意思是：我们要找的是原串中能作为套娃序列保留的最长子序列

也就是说，我们要在原串中选一个子序列，这个子序列本身是套娃序列，而且剩下的部分必须能组成一个合法括号序列（因为删除的部分要合法）

对于 (()())：

最大深度 mx=2，对应最长套娃是 (())（长度4）

删除剩下的 ()（长度2），恰好是一个合法括号序列

所以答案是 6-4=2 我们要在原串中保留最长的套娃子序列，而不是考虑能否删除整个串。

数据范围

令 $len$ 表示字符串长度：

• 部分测试点：$len \le 16$
• 部分测试点：$len \le 5000$
• 全部测试点：$1 \le len \le 3 \times 10^6$
• 字符串仅包含 ( 和 )。