题意读起来非常复杂,其实就是要我们递归或者是用栈处理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;
}