题意读起来非常复杂,其实就是要我们递归或者是用栈处理MAX表达式的计算,需要维护两个值,一个是现在计算好的总和值,另一个是现在的加号的运算次数


首先看到两个样例中:

MAX(2+1,3)
MAX(4,2+2)

这两个的运算次数为什么不一样呢?

因为3>3不成立,所以会执行后面的运算次数,后面那个3加号运算次数是0

因为4>4不成立,所以会执行后面的运算次数,后面那个2+2加号运算次数是1



所以我们将所有情况分成如下几类:

首先是a+b形状的,就比如样例中的这个数据:

MAX(MAX(1+2,3),MAX(4+5+6,MAX(7+8,9)))+MAX(10,MAX(MAX(11,12),13))
这里,a是
MAX(MAX(1+2,3),MAX(4+5+6,MAX(7+8,9)))
b是
MAX(10,MAX(MAX(11,12),13))
我们只需要找前缀括号匹配的就好,就是遇到左括号+1,右括号-1,当碰到+号且括号值为0,说明找到了+号,说明可以二分了

MAX值和cnt值进行维护就好


然后,就是MAX(a,b)的形式

那么方法同上,找到括号值为1的逗号,然后二分


最后就是最简单的形式,单个数字的,无法二分,计算下该值是多少,cnt值为0,写成递归就好


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

int T;
int MaxNum,MaxCnt;
string str;

void getans(string s,int &num,int &cnt){
	int i,j,pos,cracket=0;
	int num1,num2;
	int cnt1,cnt2;
	string s1="",s2="";
	for(i=0;i<s.length();i++)
		if (s[i]=='(') cracket++;
		else if (s[i]==')') cracket--;
		else if (cracket==0&&s[i]=='+') break;
	if (i==s.length()){
		if (s[0]>='0'&&s[0]<='9'){
			int x=0;
			for(j=0;j<s.length();j++)
				x=x*10+s[j]-'0';
			num=x;
			cnt=0;
			return;
		}
		else{
			cracket=0;
			for(j=0;j<s.length();j++)
				if (s[j]=='(') cracket++;
				else if (s[j]==')') cracket--;
				else if (cracket==1&&s[j]==',') break;
			pos=j;
			for(j=4;j<pos;j++) s1+=s[j];
			for(j=pos+1;j<s.length()-1;j++) s2+=s[j];
			getans(s1,num1,cnt1);
			getans(s2,num2,cnt2);
			//cout<<s1<<" "<<s2<<endl;
			num=max(num1,num2);
			if (num1>num2)
				cnt=cnt1*2+cnt2;
			else
				cnt=cnt1+cnt2*2;
			return;
		}
	}
	else{
		pos=i;
		for(int i=0;i<pos;i++) s1+=s[i];
		for(int i=pos+1;i<s.length();i++) s2+=s[i];
		//cout<<s1<<" "<<s2<<endl;
		getans(s1,num1,cnt1);
		getans(s2,num2,cnt2);
		num=num1+num2;
		cnt=cnt1+cnt2+1;
		return;
	}
}

int main(){
	scanf("%d",&T);
	while(T--){
		cin>>str;
		getans(str,MaxNum,MaxCnt);
		printf("%d %d\n",MaxNum,MaxCnt);
	}
	return 0;
}