fork download
copy 
  1. #define  _CRT_SECURE_NO_WARNINGS
  2. #include <iostream>
  3. #include <string>
  4. #include <algorithm>
  5. #include <vector>
  6. #include <stack>
  7. #include <deque>
  8. #include <queue>
  9. #include <utility>
  10. #include <map>
  11. #include <set>
  12. #include <functional>
  13. #include <math.h>
  14. #include <time.h>
  15. #include <fstream>
  16. #include <list>
  17. #include <climits>
  18. #include <iomanip>
  19.  
  20. using namespace std;
  21.  
  22. typedef long long int lld;
  23. typedef long double ld;
  24. typedef vector<int> vi;
  25. typedef vector<char> vch;
  26. typedef vector<lld> vlld;
  27. typedef vector<vi> vivi;
  28. typedef vector<vlld> vlvl;
  29.  
  30. lld cal(lld a, lld b, char op) //계산함수
  31. {
  32. 	lld res; 
  33.  
  34. 	switch (op)
  35. 	{
  36. 		case '+':
  37. 		{
  38. 			res = a + b;
  39.  
  40. 			break;
  41. 		}
  42. 		case '-':
  43. 		{
  44. 			res = a - b;
  45.  
  46. 			break;
  47. 		}
  48. 		case '*':
  49. 		{
  50. 			res = a * b;
  51.  
  52. 			break;
  53. 		}
  54. 	}
  55.  
  56. 	return res;
  57. }
  58.  
  59. int main()
  60. {
  61. 	cin.tie(NULL);
  62. 	ios::sync_with_stdio(false);
  63.  
  64. 	int n;
  65. 	lld mx, tmp, no = -99999999999999; //mx: 최종 답, no: 초기값
  66. 	string str;
  67.  
  68. 	cin >> n >> str;
  69.  
  70. 	int sz = n / 2 + 1; //피연산자 갯수
  71. 	vlld operand; //피연산자가 순서대로 들어갈 곳
  72. 	vlvl dp(sz + 1, vlld(4, no)); //4 X (sz + 1)
  73. 	vch opertor; //연산자가 순서대로 들어갈 곳
  74.  
  75. 	for (int i = 0; i < n; ++i)
  76. 	{
  77. 		if (i % 2)
  78. 			opertor.push_back(str[i]); //연산자 push
  79. 		else
  80. 			operand.push_back(str[i] - '0'); //피연산자 push
  81. 	}
  82.  
  83. 	dp[1][0] = operand[0]; //초기화(양수 최댓값)
  84. 	dp[1][2] = operand[0]; //초기화(양수 최솟값)
  85.  
  86. 	if (sz > 1) //피연산자가 2개 이상이라면
  87. 	{
  88. 		tmp = cal(operand[0], operand[1], opertor[0]); //첫 번째 연산자와 두 번째 연산자 계산
  89.  
  90. 		if (tmp >= 0) //양수
  91. 		{
  92. 			dp[2][0] = tmp; //양수 최댓값
  93. 			dp[2][2] = tmp; //양수 최솟값
  94. 		}
  95. 		else //음수
  96. 		{
  97. 			dp[2][1] = tmp; //음수 최솟값
  98. 			dp[2][3] = tmp; //음수 최댓값
  99. 		}
  100. 	}
  101.  
  102. 	for (int i = 3; i <= sz; ++i)
  103. 	{
  104. 		for (int j = 0; j < 4; ++j) //저장한 모든 최댓값, 최솟값에 대하여
  105. 		{
  106. 			if (dp[i - 1][j] == no) //이전 식 계산으로 도달한 값이 없으면
  107. 				continue; //pass (ex, 테케 1+5인 경우 음수 최댓값/최솟값에는 초기값이 들어있음)
  108.  
  109. 			tmp = cal(dp[i - 1][j], operand[i - 1], opertor[i - 2]); // dp[k - 1]와 1개의 추가 피연산자 계산 ex(1+5*3에서 (1+5) * 3)
  110.  
  111. 			if (tmp >= 0) //양수
  112. 			{
  113. 				dp[i][0] = max(dp[i][0], tmp); //양수 최댓값 갱신
  114. 				dp[i][2] = min(dp[i][2], tmp); //음수 최댓값 갱신
  115. 			}
  116. 			else
  117. 			{
  118. 				if (dp[i][1] == no) //초기값?
  119. 					dp[i][1] = tmp; //갱신
  120. 				else
  121. 					dp[i][1] = -max(abs(dp[i][1]), abs(tmp)); //음수 최댓값 갱신
  122.  
  123. 				if (dp[i][3] == no) //초기값?
  124. 					dp[i][3] = tmp; //갱신
  125. 				else
  126. 					dp[i][3] = -min(abs(dp[i][3]), abs(tmp)); //음수 최솟값 갱신
  127. 			}
  128. 		}
  129.  
  130. 		for (int j = 0; j < 4; ++j) //저장한 모든 최댓값, 최솟값에 대하여
  131. 		{
  132. 			if (dp[i - 2][j] == no) //이전 식 계산으로 도달한 값이 없으면
  133. 				continue; //pass (ex, 테케 1+5인 경우 음수 최댓값/최솟값에는 초기값이 들어있음)
  134.  
  135. 			tmp = cal(dp[i - 2][j], cal(operand[i - 2], operand[i - 1], opertor[i - 2]), opertor[i - 3]);// dp[k - 2]와 2개의 추가 피연산자 계산(ex 1+5*3에서 1+(5*3))
  136.  
  137. 			if (tmp >= 0) //양수
  138. 			{
  139. 				dp[i][0] = max(dp[i][0], tmp); //양수 최댓값 갱신
  140. 				dp[i][2] = min(dp[i][2], tmp); //음수 최댓값 갱신
  141. 			}
  142. 			else
  143. 			{
  144. 				if (dp[i][1] == no) //초기값?
  145. 					dp[i][1] = tmp; //갱신
  146. 				else
  147. 					dp[i][1] = -max(abs(dp[i][1]), abs(tmp)); //음수 최댓값 갱신
  148.  
  149. 				if (dp[i][3] == no) //초기값?
  150. 					dp[i][3] = tmp; //갱신
  151. 				else
  152. 					dp[i][3] = -min(abs(dp[i][3]), abs(tmp)); //음수 최솟값 갱신
  153. 			}
  154. 		}
  155. 	}
  156.  
  157. 	for (int i = 0; i < 4; ++i)
  158. 		mx = max(mx, dp[sz][i]); // 저장한 4개의 값 중 최댓값 산출
  159.  
  160. 	cout << mx << '\n';
  161.  
  162. 	return 0;
  163. }
  164.  
Success #stdin #stdout 0s 4484KB
comments (?)
stdin
copy 
1
1
stdout
copy 
17960880
https://ideone.com/Xtg4dE
language:
C++14 (clang 8.0)
created:
3 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!