本文主要是介绍ACM-ICPC 2018 沈阳赛区网络预赛 B Call of Accepted，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
ACM-ICPC 2018 沈阳赛区网络预赛
- 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的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
