首页 > 其他 > 详细

Compressed Bracket Sequence(cf1556C)

时间:2021-09-06 04:44:51      阅读:19      评论:0      收藏:0      [点我收藏+]

Compressed Bracket Sequence

(https://codeforces.com/contest/1556/problem/C)

题意:

给定一个数组,下标为奇数的表示左括号连续数目,反之则表示右括号连续数目,求有多少个区间满足的括号满足正则表达式

思路:

我们可以计算从l+1到r?1段上的最小支架平衡。最小括号平衡是我们必须放置在括号序列之前的最小开始括号数量,以使它是规则的,前提是我们可以在末尾放置任意数量的结束括号。让我们将这个数字表示为minBalance,并将- cl+1+cl+2 - cl+2+…的总和表示为balance。

下观察,如果我们解决开括号取自cl的数量,然后我们可以计算括号的数量,我们应该从cr。使用这些观察我们可以计算的答案l . . r使用以下公式:min (cl, cr?balance)?max(minBalance) + 1。

代码:

#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) x & -x
#define int long long
const int N=1100;
int a[N];
signed main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];

	}
	int cnt=0;
	for(int i=1;i<=n;i+=2){
		int sum=0;int l=0;
		for(int j=i+1;j<=n;j++){
			if(j%2==0){
				int ll=-l;
				ll=max(1ll,ll);
				ll=max(ll,1-sum);
				int r=min(a[i],a[j]-sum);//a[j]减去之前留下的左括号代表还剩的右括号和a[i]的左括号取小值; 
				if(r>=ll) cnt+=r-ll+1;//减去最少要添加左括号的数目后 
			}
			if(j%2) sum+=a[j];
			else sum-=a[j];
			l=min(l,sum);//在最前面至少要添加多少有个左括号 
		}
	}
	cout<<cnt<<endl;
}

Compressed Bracket Sequence(cf1556C)

原文:https://www.cnblogs.com/CurryBP/p/15228211.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!