• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

CF 5C Longest Regular Bracket Sequence

开发技术 开发技术 1周前 (05-02) 6次浏览

题目链接
思路
关键在于想到括号匹配用栈维护的一个过程。
求最长的子串,所以每一个右括号尽可能匹配能匹配的最近的左括号。
(dp[i]):第i位向左匹配能匹配到的最长距离。
若当前位置(s[i]=))(stack.size()>0),那么就说明当前位置的右括号可以匹配到左括号,到这一位的最长距离即是(dp[i]=i-stack.top()+1+dp[stack.top()-1])
代码

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef pair<int, int> PII;
const int N = 1e6 + 10;

char s[N];
int dp[N];
stack<int> stk;

void solve() {
	scanf("%s", s + 1);
	int len = strlen(s + 1);
	int mx = 0, cnt = 1;
	for(int i = 1; i <= len; i++) {
		if(s[i] == '(') stk.push(i);
		else {
			if(stk.size() > 0) {
				dp[i] = i - stk.top() + 1 + dp[stk.top() - 1];
				stk.pop();
				if(mx < dp[i]) mx = dp[i], cnt = 1;
				else if(mx == dp[i]) cnt++;
			}
		}
	}
	printf("%d %dn", mx, cnt);
}

int main() {
	// freopen("in.txt", "r", stdin);
	// int t; cin >> t; while(t--)
	solve();
	return 0;
}

程序员灯塔
转载请注明原文链接:CF 5C Longest Regular Bracket Sequence
喜欢 (0)