盒子
盒子
文章目录
  1. 题目
  2. 题意
  3. 思路
  4. 代码
  5. 更新日志

CF 5C Longest Regular Bracket Sequence (贪心)

题目

源地址:http://codeforces.com/problemset/problem/5/C

题意

给定一串括号,长度为$n$, 求最长的能够匹配的(符合规则)的子序列,输出最长的长度,以及该长度的个数。如果没有匹配的,输出0 1
数据范围:$1{\leq}n{\leq}10^6$

思路

对于字符串串中的每个’)’我们定义两个值:

  1. pos[i]表示’)’对应匹配的’(‘的位置,如果不匹配则为-1。pos[i]可以用栈来存储’(‘的位置实现。
  2. f[i]表示以该’)’结尾能够匹配的最长子序列。
    首先,我们可以知道如果pos[i]不等于-1,那么(pos[i], i)这个子串一定可以。
    其次,如果上述符合,再观察pos[i] - 1的位置,如果该位置也为’)’,且也被匹配到了,那么该子序列就可以继续向前匹配到f[pos[i] - 1]

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
const int N = 1e6 + 10;
char str[N];
int pos[N], f[N];
int main () {
gets(str);
int n = strlen(str);
int mx = 0, m = 1, cnt = 0;
for (int i = 1; i <= n; i++) {
if (str[i - 1] == '(') pos[++cnt] = i;
else {
if (!cnt) continue;
f[i] = f[pos[cnt] - 1] + i - pos[cnt] + 1;
cnt--;
if (f[i] > mx) mx = f[i], m = 1;
else if (f[i] == mx) m++;
}
}
cout<<mx<<" "<<m<<endl;
return 0;
}

更新日志

  • 2014-11-9 AC