Codeforces Beta Round #5 C. Longest Regular Bracket Sequence 括号序列 dp+栈

点击打开链接

题意：

给你一个括号序列，让你找到最长的连续的合法括号序列

然后让你输出这个括号序列的长度是多少

这么长的括号序列一共有多少个

思路：

看到括号匹配，就用stack来弄就好了

然后我们dp一下，表示以这个字符结尾的序列的长度是多少

dp[i] += dp[k.top()-1]; 从当前合法序列的最左边'('的左边的位置转移，如果是'(',dp[k.top()-1]=0,否则 dp[k.top()-1]就是上一个合法序列的长度，比如：(())()就要加上4，当然也可能是0，比如：(()))()

代码：

//http://codeforces.com/PRoblemset/problem/5/C#include <bits/stdc++.h>using namespace std;typedef long long ll;const int maxn = 1e6+10;const int INF = 0x3f3f3f3f;const ll INFLL = 0x3f3f3f3f3f3f3f3fLL;inline ll read(){    ll x=0,f=1;char ch=getchar();    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}    return x*f;}//////////////////////////////////////////////////////////////////////////stack<int> k;string s;ll dp[maxn];int main(){	cin >> s;	for(int i=0; i<s.size(); i++){		if(s[i] == '(')			k.push(i);		else{			if(!k.empty()){				dp[i] = i-k.top()+1;				if(k.top() > 0) 					dp[i] += dp[k.top()-1]; // 从当前合法序列的最左边'('的左边的位置转移				k.pop();			}		}	}	// for(int i=0; i<s.size(); i++)	// 	cout << dp[i] << " ";	// cout << endl;	int ans1 = 0, ans2;	for(int i=0; i<s.size(); i++){		if(dp[i] > ans1){			ans1 = dp[i];			ans2 = 1;		}else if(dp[i]==ans1){			ans2 ++;		}	}	if(ans1 == 0)		cout << "0 1/n";	else		cout << ans1 << " " << ans2 << endl;    return 0;}