链接
传送门
题意
给出一个由括号组成的字符串。输出最长规范子串的长度，并输出其个数。长度为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;
}
|