开始 2020-05-17 12:00:00

517编程5月月赛-普及组

结束 2020-05-17 14:30:00
Contest is over.
当前 2020-07-03 23:52:02

E. 括号匹配

描述

仅由括号 “ ( ” 和 “ ) ” 组成的字符串称为括号序列。所有括号都能匹配的序列称为正确的括号序列。 
现有一个由括号和问号组成的字符串s,可以用“( ”或“ )”替换每个问号。问有多少子串能够成为正确的括号序列(空串不算)。

输入

字符串$s$,该字符串仅由字符'(',')'和'?'组成 (假设字符串长度为$n,2\leq n\leq 5000$)。 
 

输出

输出一个整数,表示能够成为正确的括号序列的子串个数。

样例

输入

((?))

输出

4

输入

??()??

输出

7

输入

??

输出

1

提示

对于第一个测试用例,能够成为正确的括号序列的子串为: 
1.可以转换为“()”的“(?”。 
2.可以转换为“()”的“?)”。 
3.可以转换为“(())”的“((?)”。 
4.可以转换为“(())”的“(?))”。 


对于第二个测试用例,能够成为正确的括号序列的子串为: 
1.可以转换为“()”的“??” 。 
2.“()”。 
3.可以转换为“()()”的“ ??()”。 
4.可以转换为“(())”的“?()?” 。 
5.可以转换为“()”的“??” 。 
6.可以转换为“()()”的“()?” 。 
7.可以转换为“()()()”的“??()??” 。

 

对于30%的测试点,$2\leq n \leq 10$;

对于60%的测试点,$2\leq n \leq 100$;

对于100%的测试点,$2\leq n \leq 5000$;

时间限制 1 秒
内存限制 256 MB