Codeforces 5C Longest Regular Bracket Sequence

链接

传送门

题意

给出一个由括号组成的字符串。输出最长规范子串的长度,并输出其个数。长度为0时输出个数为1。

思路

定义状态$d[i]$为以第$i$个字符为结尾的规范子串的长度。显然,左括号不能做结尾,只考虑当前字符为右括号的情况。当第$i-1-d[i-1]$个能与第$d[i]$个匹配时,$d[i]=d[i-1]+d[i-1-d[i-1]-1]$;不匹配时$d[i]=0$。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int inf = 0x3f3f3f3f;
const int maxn = 1000010;
int d[maxn];
char s[maxn];
int main() {
scanf("%s", s + 1);
int n = int(strlen(s + 1));
int ans = 0, num = 0;
for (int i = 1; i <= n; ++i) {
if (s[i] == '(') continue;
int pos = i - d[i - 1] - 1;
if (pos > 0 && s[pos] == '(') {
d[i] = d[i - 1] + 2;
if (pos > 1) {
d[i] += d[pos - 1];
}
}
if (d[i] > ans) {
ans = d[i];
num = 0;
}
if (d[i] == ans) {
++num;
}
}
if (ans == 0) {
num = 1;
}
printf("%d %d", ans, num);
return 0;
}