fork(4) download
copy 
  1. #include <bits/stdc++.h>
  2. #define MAXN 105
  3. using namespace std;
  4.  
  5. int main()
  6. {
  7. 	int t;
  8. 	scanf("%d", &t);
  9. 	while (t--) {
  10. 		string str;
  11. 		cin >> str;
  12.  
  13. 		vector<int> nums;
  14. 		vector<char> ops;
  15. 		for (int i = 0; i < str.length(); i++) {
  16. 			if (i & 1)
  17. 				ops.push_back(str[i]);
  18. 			else
  19. 				nums.push_back((int)(str[i] - '0'));
  20. 		}
  21.  
  22. 		vector<vector<long long> > max_cost(nums.size() + 1, vector<long long>(nums.size() + 1, 0));
  23. 		vector<vector<long long> > min_cost(nums.size() + 1, vector<long long>(nums.size() + 1, LLONG_MAX));
  24. 		for (int i = 0; i <= nums.size(); i++)
  25. 			max_cost[i][i] = min_cost[i][i] = nums[i];
  26.  
  27. 		for (int l = 2; l < nums.size() + 1; l++) {
  28. 			for (int i = 0; i < nums.size() - l + 1; i++) {
  29. 				int j = i + l - 1;
  30. 				for (int k = i; k < j; k++) {
  31. 					long long tmp_mx, tmp_mn;
  32. 					if (ops[k] == '+') {
  33. 						tmp_mn = min_cost[i][k] + min_cost[k + 1][j];
  34. 						tmp_mx = max_cost[i][k] + max_cost[k + 1][j];
  35. 					}
  36. 					else {
  37. 						tmp_mn = min_cost[i][k] * min_cost[k + 1][j];
  38. 						tmp_mx = max_cost[i][k] * max_cost[k + 1][j];
  39. 					}
  40. 					min_cost[i][j] = min(min_cost[i][j], tmp_mn);
  41. 					max_cost[i][j] = max(max_cost[i][j], tmp_mx);
  42. 				}
  43. 			}
  44. 		}
  45.  
  46. 		printf("%lld %lld\n", max_cost[0][nums.size()-1], min_cost[0][nums.size()-1]);
  47. 	}
  48. }
Success #stdin #stdout 0s 3436KB
comments (?)
stdin
copy 
1
1+2*3+4*5
stdout
copy 
105 27
https://ideone.com/F6sxP4
language:
C++ (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!