ACM-ICPC 2018 沈阳赛区网络预赛 B Call of Accepted

本文主要是介绍ACM-ICPC 2018 沈阳赛区网络预赛 B Call of Accepted，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

ACM-ICPC 2018 沈阳赛区网络预赛

1. Call of Accepted

题意：给定字符串，字符串有 +  -  *  d  (  )  还有数字，表示一个运算式子，d 表示一种新运算符，x d y 表示 最小为 x 最大 为 x*y ，求字符串能表示的最大值。

#include <bits/stdc++.h>
using namespace std;int len;
int fst[1005];
char str[1005];pair<int,int> add(pair<int,int>p1, pair<int,int>p2) {return make_pair(p1.first+p2.first, p1.second+p2.second);
}
pair<int,int> sub(pair<int,int>p1, pair<int,int>p2) {return make_pair(p1.first-p2.second, p1.second-p2.first);
}
pair<int,int> mul(pair<int,int>p1, pair<int,int>p2) {int t1 = p1.first*p2.first;int t2 = p1.first*p2.second;int t3 = p1.second*p2.first;int t4 = p1.second*p2.second;return make_pair(min(min(t1,t2), min(t3,t4)), max(max(t1,t2),max(t3,t4)));
}pair<int,int> pp(pair<int,int>p1, pair<int,int>p2) {return make_pair(p1.first, p1.second*p2.second);
}pair<int,int> Jud(int begin, int end)
{ int i;pair<int,int> k;for(i = begin; i <= end; i++) {if(str[i]== '+' && fst[i] == fst[begin]){//	cout <<"#"<<endl;k = add(Jud(begin, i - 1), Jud(i + 1, end));return k;}}for(i = end; i >= begin; i--){if(str[i]=='-' && fst[i] == fst[begin]){//    cout << "#" <<endl;k = sub(Jud(begin, i - 1), Jud(i + 1, end)); //     cout << i <<"*"<<endl;return k;}}for(i = begin; i <= end; i++){if(str[i] == '*' && fst[i] == fst[begin]){k = mul(Jud(begin, i - 1), Jud(i + 1, end)); return k;}}for (int i = end; i >= begin; i--) {if (str[i] == 'd' && fst[i] == fst[begin]) {k = pp(Jud(begin, i - 1), Jud(i + 1, end)); return k;}}if(str[begin]=='(') {// for(i = begin + 1; fst[i] >= fst[begin + 1]; i++);//  cout << begin+1 << "* " << i-1 << endl;k = Jud(begin + 1, end - 1);}else{int n = 0;for (int i = begin; i <= end; i++) {if (!(str[i] >= '0' && str[i] <= '9'))break;n = n*10 + str[i] -'0';}k = make_pair(n, n);}return k;
}int main()
{int  i;while(cin>>str){memset(fst, 0, sizeof(fst));len = strlen(str);fst[0] = 1;//   printf("%d ",fst[0]);for(i = 1; i <= len - 1; i++){                           if(str[i - 1]== '(')   fst[i] = fst[i - 1] + 1;else if(str[i] == ')')fst[i] = fst[i - 1] - 1;elsefst[i] = fst[i - 1];//        printf("%d ",fst[i]);}//    puts("");pair<int,int> ans = Jud(0, len - 1); printf("%d %d\n", ans.first, ans.second);}return 0;
}

 

这篇关于ACM-ICPC 2018 沈阳赛区网络预赛 B Call of Accepted的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---