Codeforces远古场 Longest Regular Bracket Sequence (动态规划)

本文主要是介绍Codeforces远古场 Longest Regular Bracket Sequence (动态规划)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Longest Regular Bracket Sequence

题面翻译

给出一个括号序列，求出最长合法子串和它的数量。
合法的定义：这个序列中左右括号匹配

题目描述

This is yet another problem dealing with regular bracket sequences.

We should remind you that a bracket sequence is called regular, if by inserting «+» and «1» into it we can get a correct mathematical expression. For example, sequences «(())()», «()» and «(()(()))» are regular, while «)(», «(()» and «(()))(» are not.

You are given a string of «(» and «)» characters. You are to find its longest substring that is a regular bracket sequence. You are to find the number of such substrings as well.

输入格式

The first line of the input file contains a non-empty string, consisting of «(» and «)» characters. Its length does not exceed $ 10^{6} $ .

输出格式

Print the length of the longest substring that is a regular bracket sequence, and the number of such substrings. If there are no such substrings, write the only line containing “0 1”.

样例 #1

样例输入 #1

)((())))(()())

样例输出 #1

6 2

样例 #2

样例输入 #2

))(

样例输出 #2

0 1

---

考虑这道题的DP方法。
不难想出，要用 $f[i]$ 来表示前 $i$ 段里面最长的合法括号序列，现在来考虑能够怎么DP。

合法的序列可以有以下两种情况：

• ((()))，也就是单个大括号
• ()()(())，也就是多个括号

那么对于单个大括号当然就很好维护，他的长度就可以算为最右边的右括号的下表减去最左边的左括号的下表加1，在这种情况下不需要状态转移。

对于多个括号的情况，我们要考虑状态转移。
由于我们在维护段落的合理性的时候是通过栈来维护的，我们用以下变量来实现数组模拟栈stk[N]为栈本身 tt为栈顶，在检测到左括号的时候我们会压入他的下标，那么取出的时候一定是最左边的右括号先去对应最右边的左括号，知道堆中元素全部弹出。

那么我们可以每次检查一下f[stk[tt] - 1]是否有元素，如果有的话就说明了当前右括号对应的左括号的左边是有另一组合理括号段的，那么就加上他。
因为题目要求要记录数量，所以我们使用cnt数组进行各个段落的最长合理子段的数量记录。
那么最终的状态转移方程就是：++cnt[f[i] = i - stk[tt] + 1 + f[stk[tt--] - 1]]

---

CODE：

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
#define endl '\n'int stk[N];
int tt = -1;
int f[N];
int cnt[N];int main(){string s;cin >> s;for(int i = 0;i < s.size();i++){if(s[i] == '(')stk[++tt] = i;else if(~tt) ++cnt[f[i] = i - stk[tt] + 1 + f[stk[tt--] - 1]];}cnt[0] = 1;for(int i = s.size();~i;i--){if(cnt[i]){cout << i << " " << cnt[i] << endl;return 0;}}return 0;
}

这篇关于Codeforces远古场 Longest Regular Bracket Sequence (动态规划)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---