Algorithm/Problem Solving
[BOJ/11054] 가장 긴 바이토닉 부분 수열
DevMoomin
2020. 4. 19. 20:14
(공감과 댓글 하나는 글쓴이에게 큰 힘이 됩니다.)
문제 링크
- https://www.acmicpc.net/problem/11054
사용 알고리즘
- DP
풀이
- d1[i] = a[i]를 가장 마지막으로 하는 가장 긴 증가하는 부분 수열의 길이
- d2[i] = a[i]를 가장 마지막으로 하는 가장 긴 감소하는 부분 수열의 길이
- d[i] = d1[i] + d2[i] - 1
→ i가 겹치게 되므로 -1 처리
소스 코드
- https://github.com/moomini/algorithm/blob/master/boj/11054.cpp
|
#include <cstdio>
int d1[1003], d2[1003];
int a1[1003], a2[1003];
int main(void) {
int n; scanf("%d", &n);
for (int i = 0; i < n; ++i) {
scanf("%d", &a1[i]);
a2[n - i - 1] = a1[i];
}
for (int i = 0; i < n; ++i) {
d1[i] = 1;
d2[i] = 1;
for (int j = 0; j < i; ++j) {
if ((a1[i] > a1[j]) && (d1[j] + 1 > d1[i])) d1[i] = d1[j] + 1;
if ((a2[i] > a2[j]) && (d2[j] + 1 > d2[i])) d2[i] = d2[j] + 1;
}
}
int ans = -1;
for (int i = 0; i < n; ++i) {
if (ans < (d1[i] + d2[n - i - 1] - 1)) ans = d1[i] + d2[n - i - 1] - 1;
}
printf("%d\n", ans);
return 0;
}
|