https://www.acmicpc.net/problem/11054
문제
수열 S가 어떤 수 Sk를 기준으로 S1 < S2 < ... Sk-1 < Sk > Sk+1 > ... SN-1 > SN을 만족한다면, 그 수열을 바이토닉 수열이라고 한다.
예를 들어, {10, 20, 30, 25, 20}과 {10, 20, 30, 40}, {50, 40, 25, 10} 은 바이토닉 수열이지만, {1, 2, 3, 2, 1, 2, 3, 2, 1}과 {10, 20, 30, 40, 20, 30} 은 바이토닉 수열이 아니다.
수열 A가 주어졌을 때, 그 수열의 부분 수열 중 바이토닉 수열이면서 가장 긴 수열의 길이를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000)
출력
첫째 줄에 수열 A의 부분 수열 중에서 가장 긴 바이토닉 수열의 길이를 출력한다
LIS, LDS에 대해 각 원소를 시작점/끝점으로 했을 때 길이를 memoization한다
단 LIS는 뒷 LIS들을 참조하며 이 원소가 앞머리에 붙어도 되는지를 검사하며 구한다.
단 각 LDS는 앞 LDS들을 참조하며 이 원소가 꼬리에 붙어도 되는지를 검사하며 구한다.
마지막에 각 원소에 대한 LIS+LDS-1이 가장 긴 바이토닉 수열의 길이이다.
#include<iostream>
#include<algorithm>
using namespace std;
//lis lds 같이
int main() {
int n;
cin >> n;
int *a = new int[n];
for (int i = 0; i < n; i++) {
cin >> a[i];
}
int *b = new int[n];
b[0] = 1;
//lds구함
for (int i = 0; i <= n - 1; i++) {
b[i] = 1;
for (int j = 0; j < i; j++) {
if (a[j] < a[i]) {
b[i] = max(b[i], b[j] + 1);
}
}
}
//뒤에서부터 작은 LiS 계산(나로부터 시작하는)
int *c = new int[n];
c[n - 1] = 1;
for (int i = n - 1; i >= 0; i--) {
int diff = n - 1 - i;//i== n-2면 diff==1
c[i] = 1;//나 자신이 b[i]인 경우
for (int j = 1; j <= diff; j++) {
//b[i+j]중 나랑 매치되는 것 중 가장 큰 것 찾기
//만약 못찾는다면 나 자신이 b[i]가 된다
if (a[i + j] < a[i]) {
c[i] = max(c[i], c[i + j] + 1);
}
}
}
int res = 0;
for (int i = 0; i < n; i++) {
res = max(res, b[i] + c[i]-1);
}
cout << res << endl;
/*
for (int i = n - 1; i >= 0; i--) {
cout << "i는 \t" << i << "\t" << b[i] << "\t"<<c[i]<< endl;
}
*/
//b[0]가 답이 아니다!!!!
delete[] a;
delete[] b;
delete[] c;
}