일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
Tags
- off by one
- ROP
- 큐
- DFS
- BOF
- tcache
- 브루트 포스
- 완전 탐색
- 수학
- 문자열 처리
- BFS
- 포맷스트링버그
- OOB
- 스택
- 이진 탐색
- 이분 탐색
- 투 포인터
- 스위핑 알고리즘
- syscall
- fsb
- 연결리스트
- 동적 계획법
- RTL
- 이진트리
- 백트래킹
- 다이나믹 프로그래밍
- 에라토스테네스의 체
- 분할 정복
- House of Orange
- heap
Archives
- Today
- Total
SDJ( 수돈재 아님 ㅎ )
[C++] 11054 - 가장 긴 바이토닉 부분 수열 본문
문제 링크 : https://www.acmicpc.net/problem/11054
11054번: 가장 긴 바이토닉 부분 수열
첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000)
www.acmicpc.net
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 48 49 50 51 52 53 54 | #include<iostream> #include<algorithm> #define endl '\n' #define max(A, B) (A > B ? A : B) using namespace std; int A[1005]; int dp[1005]; int dp2[1005]; int main(void) { int n; int mc,mc2; int save_max = 0; ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> n; for(int i = 0; i < n; ++i) cin >> A[i]; dp[0] = dp2[n-1] = 1; for(int i = 0; i < n; ++i) { mc = dp[0]; for(int j = 0; j < i; ++j) if(A[i] > A[j]) mc = max(mc, dp[j]+1); dp[i] = mc; } for(int i = n-1; i >= 0; --i) { mc2 = dp2[n-1]; for(int j = n-1; j >= i; --j) if(A[i] > A[j]) mc2 = max(mc2, dp2[j]+1); dp2[i] = mc2; } for(int i = 0; i < n; ++i) if(dp[i]+dp2[i]-1 > save_max) save_max = dp[i] + dp2[i] -1; cout << save_max << endl; return 0; } http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter |
'알고리즘 > Backjoon' 카테고리의 다른 글
[C++] 12865 - 평범한 배낭 (0) | 2019.12.23 |
---|---|
[C++] 2565 - 전깃줄 (0) | 2019.12.23 |
[C++] 1051 - 숫자 정사각형 (0) | 2019.12.19 |
[C++] 1012 - 유기농 배추 (0) | 2019.12.19 |
[C++] 1182 - 부분수열의 합 (0) | 2019.12.15 |
Comments