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