728x90
가장 긴 바이토닉 부분 수열
https://www.acmicpc.net/problem/11054
<코드>
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 | #include <stdio.h> int main(void){ int N; int Dp[2][1010] = {}; int A[1010] = {}; int max = 0; scanf("%d", &N); for (int i = 1; i <= N; i++) scanf("%d", &A[i]); for (int i = 1; i <= N; i++) { int maxA = 0; for (int j = 0; j < i; j++){ if (A[i]>A[j]){ if (maxA < Dp[0][j]) maxA = Dp[0][j]; } } Dp[0][i] = maxA + 1; } for (int i = N; i >= 1; i--) { int maxA = 0; for (int j = N; j > i; j--){ if (A[i]>A[j]){ if (maxA < Dp[1][j]) maxA = Dp[1][j]; } } if (Dp[1][i]<maxA + 1) Dp[1][i] = maxA + 1; } for (int i = 1; i <= N; i++){ if (max < Dp[0][i] + Dp[1][i]) max = Dp[0][i] + Dp[1][i]; } printf("%d\n", max-1); } | cs |
<문제 푼 요령>
1. 이건 '가장 긴 증가하는 부분 수열'을 두 번 사용해서 풀면 된다.
2. -> 오른쪽 방향으로 진행을 한번 하고 <- 왼쪽 방향으로 진행을 하여서 그 두개의 Dp 배열의 합이 최대가 되는 곳이 가장 긴 바이토닉 수열이 되는 것이다.
3. 하지만 자기자신을 둘다 가지고 있기 때문에 -1값을 해야한다.
728x90
'Algorithm > DP(동적 계획법)' 카테고리의 다른 글
[백준][2579번][DP] 계단 오르기 (1) | 2016.04.14 |
---|---|
[백준][1912번][DP] 연속합 (4) | 2016.04.14 |
[백준][11722번][DP] 가장 긴 감소하는 부분 수열 (0) | 2016.04.14 |
[백준][11055번][DP] 가장 큰 증가 부분 수열 (0) | 2016.04.14 |
[백준][11053번][DP] 가장 긴 증가 부분 수열 (4) | 2016.04.14 |
댓글