fork download 
  1. #define _CRT_SECURE_NO_WARNINGS
  2.  
  3. #include <iostream>
  4. #include <cstdlib>
  5. #include <cmath>
  6. #include <algorithm>
  7. #include <climits>
  8. #include <cstring>
  9. #include <string>
  10. #include <vector>
  11. #include <queue>
  12. #include <deque>
  13. #include <stack>
  14. #include <map>
  15. #include<iomanip>
  16.  
  17. using namespace std;
  18.  
  19. /*
  20. - endl 대신 '\n' 사용하기
  21. - cin.tie(0) 사용
  22. - 테스트 케이스 있는 문제일 시 전역변수 초기화 신경쓰기
  23. - (A + B + C) % D = ((A + B) % D + C) % D
  24. - 문자열 출력 문제는 정답 문자열 복사해서 코드에 넣기
  25. - 괄호 사용 유의하기
  26. - 문자열은 함수로 넘길 때 const & 잘 사용하기
  27.  
  28. - 최악의 경우 int 값 초과하는지, 배열 인덱스 초과하는지 확인
  29. - n 범위 확인 (0인 경우), 양수음수 정수소수 확인, 불가케이스 -1 출력 등 확인
  30. - 큰 배열 선언 시 전역선언, 테케 많을 시 초기화, 배열 용량 max N + 5
  31. */
  32.  
  33. #define MOD 1000000007
  34. #define INT_MAX 987654321
  35. #define MAX 100005
  36.  
  37. typedef long long int ll;
  38. typedef pair<int, int> pii;
  39. int N;
  40. int arr[1001];
  41. int dp_ascending[1001];
  42. int dp_descending[1001];
  43. int dp_bitonic[1001];
  44. // 테스트 케이스 초기화 시
  45. void init()
  46. {
  47. 	for (int i = 1; i <= N; i++) {
  48. 		dp_ascending[i] = 1;
  49. 		dp_descending[i] = 1;
  50. 		dp_bitonic[i] = 1;
  51. 	}
  52. }
  53.  
  54. int main()
  55. {
  56. 	ios_base::sync_with_stdio(false);
  57. 	cin.tie(0);
  58. 	cout.tie(0);
  59. 	cin >> N;
  60.  
  61. 	init();
  62. 	for (int i = 1; i <= N; i++) {
  63. 		cin >> arr[i];
  64. 	}
  65. 	for (int i = 1; i <= N; i++) {
  66. 		int max_val = dp_ascending[i];
  67. 		for (int j = 1; j <= i; j++) {
  68. 			if (arr[i] > arr[j]) {
  69. 				if (max_val < dp_ascending[j] + 1) {
  70. 					max_val = dp_ascending[j] + 1;
  71. 				}
  72. 			}
  73. 		}
  74. 		dp_ascending[i] = max_val;
  75. 	}
  76.  
  77. 	for (int i = N; i >= 1; i--) {
  78. 		int max_val = dp_descending[i];
  79. 		for (int j = i; j <= N; j++) {
  80. 			if (arr[i] > arr[j]) {
  81. 				if (max_val < dp_descending[j] + 1) {
  82. 					max_val = dp_descending[j] + 1;
  83. 				}
  84. 			}
  85. 		}
  86. 		dp_descending[i] = max_val;
  87. 	}
  88.  
  89. 	for (int i = 1; i < N; i++) {
  90. 		if (arr[i] != arr[i + 1]) {
  91. 			dp_bitonic[i] = dp_ascending[i] + dp_descending[i + 1];
  92. 		}
  93. 		else {
  94. 			dp_bitonic[i] = max(dp_ascending[i], dp_descending[i]);
  95. 		}
  96. 	}
  97.  
  98. 	int max_val = 1;
  99. 	for (int i = 1; i < N; i++) {
  100. 		if (max_val < dp_bitonic[i]) {
  101. 			max_val = dp_bitonic[i];
  102. 		}
  103. 	}
  104. 	cout << max_val << '\n';
  105. 	return 0;
  106. }
  107. //
  108. //5 1 4 4 2 3 2 1 1 1
  109. //1 5 2 1 4 3 3 3 2 1
  110. //1 1 1 1 1 1 1 1 1 1
  111.  
Success #stdin #stdout 0s 4988KB
comments (?)
stdin 
5
2 1 1 1 1
stdout 
2
https://ideone.com/tsFHhl
language:
C++ (gcc 8.3)
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!