May_Day训练赛模拟题 HDOJ 3350 #define is unsafe

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

MAX(MAX(1+2,3),MAX(4+5+6,MAX(7+8,9)))

MAX(10,MAX(MAX(11,12),13))

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;
}