托米的简单表示法

输入的第一行包含一个整数T，表示指定测试用例的数量。
每个测试用例前面都有一个空白行。
每个测试用例由一个合法括号序列组成。每行只包含字符'('和')'。

C++11(clang++ 3.9) 解法, 执行用时: 15ms, 内存消耗: 2384K, 提交时间: 2018-06-01 23:09:56

#include<bits/stdc++.h>
using namespace std;
const int maxn=4e5+5;
using LL=long long;
LL line[maxn];
LL high[maxn];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	string s;
	int T,i,j,x;
	LL ans;
	cin>>T;
	while(T--)
	{
		cin>>s;
		x=0;
		ans=0;
		for(i=0;i<s.length();i++)
		{
			if(s[i]=='(')
			{
				line[x]=i;
				high[x]=1;
				x++;	
			}
			else
			{
				LL xx=high[x-1]*(i-line[x-1]);
				if(x&1)
					ans+=xx;
				else
					ans-=xx;
				if(x>1)high[x-2]=max(high[x-2],high[x-1]+1);
				x--;
			}
		}
		cout<<ans<<endl;
	}
	return 0;
	
}

C++14(g++5.4) 解法, 执行用时: 22ms, 内存消耗: 7912K, 提交时间: 2018-06-01 22:49:24

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=4e5+8;
char s[N];
int h[N],w[N];
long long sum[N];
int dfs(int i){
	w[i]=h[i]=1;
	int j=i+1,nxt;
	sum[i]=0;
	for(;s[j]!=')';j=nxt){
		nxt=dfs(j);
		sum[i]+=sum[j];
		w[i]+=w[j]+1;
		h[i]=max(h[i],h[j]+1);
	}
	sum[i]=1LL*w[i]*h[i]-sum[i];
	return j+1;
	
}
int main(){
	int T;
	for(scanf("%d",&T);T--;){
		scanf("%s",s);
		long long ans=0;
		for(int i=0;s[i];){
			int nxt=dfs(i);
			ans+=sum[i];
			i=nxt;
		}
		printf("%lld\n",ans);
	}
}

详情