다이나믹 프로그래밍

가장 긴 바이토닉 부분 수열 (중요!)

4gats 2023. 3. 30. 17:34

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
55
56
57
#include <iostream>
 
int a[1004];
int inc[1004];
int de[1004];
int d[1004];
 
using namespace std;
 
int main()
{
    int n;
    cin >> n;
 
    for (int i = 1; i <= n; i++)
        cin >> a[i];
 
    for (int i = 1; i <= n; i++)
    {
        inc[i] = 1;
        for (int j = 1; j <= i; j++)
        {
            if (a[j] < a[i])
            {
                if (inc[j] < inc[i])
                    continue;
                else
                    inc[i] = inc[j] + 1;
            }
        }
        
    }
 
    for (int k = n; k >= 1; k--)
    {
        de[k] = 1;
        for (int j = k + 1; j <= n; j++)
        {
            if (a[k] > a[j] && de[k] < de[j] + 1)
                de[k] = de[j] + 1;
        }
    }
 
    for (int i = 1; i <= n; i++)
    {
        d[i] = inc[i] + de[i] - 1;
    }
    
    int ans = d[1];
    for (int i = 1; i <= n; i++)
    {
        if (ans < d[i])
            ans = d[i];
    }
 
    cout << ans << '\n';
}
 cs