---
title
Quy hoạch động (Phần 2) - Lời giải
---

Quy hoạch động (Phần 2) - Lời giải
===

---

###### ✍️ Author: 2School Guideline
###### 📋 Content:
[TOC]

---

# [CSES - Towers](https://cses.fi/problemset/task/1073)
## Đề bài
- Cho $n$ khối lập phương có kích thước lần lượt là $k_1, k_2, k_3, ..., k_n.
- Một tòa thấp là dãy khối lập phương (có thể không liên tiếp) được chọn phải thỏa mãn các khối lập phương liền kề nhau được chọn khối ở dưới **lớn hơn** khối ở trên.
- Đếm số dãy ít nhất cần sử dụng để ghép $n$ khối lại phương lại thành các tòa tháp.
### Input
- Dòng đầu gồm số nguyên dương $n$ là số khối lập phương ($n \leq 2 \cdot 10^5$).
- Dòng tiếp theo gồm $n$ số nguyên dương là kích thước của $n$ khối lập phương : $k_1, k_2, k_3, ..., k_n$ ($k_i \leq 10^9$).
### Output
- Gồm $1$ số nguyên dương duy nhất là số tòa tháp ít nhất.
### Sample Input

5
3 8 2 1 5

### Sample Output

2

### Giải thích
- Tòa tháp thứ nhất gồm $3$ khối lập phương có kích thước : $3 \ 2 \ 1$.
- Tòa tháp thứ hai gồm $2$ khối lập phương có kích thước : $8 \ 5$.
## Lời giải
:::spoiler **Ý tưởng**
- Đầu gọi dãy $b$ gồm $k$ số nguyên dương được **sắp xếp** không giảm là giá trị cuối cùng của các tòa tháp đã xây : $b_1 < b_2 < b_3 < ... < b_k$.
- Khi xét tới khối lập phương thứ $i$, nếu tồn tại vị trí $j$ sao cho $b_j > a_i$ mà $j$ là nhỏ nhất thì ta sẽ thay thế $b_j = a_i$ tức là ta thêm $a_i$ vào chồng thứ $j$. Ngược lại ta thêm vào dãy $b$ khối lập phương $a_i$ (tức là không thể ghép $a_i$ với bất kì tòa tháp nào). Vì sao cách này lại hiệu quả và chính xác ?
- **Chứng minh :** Nhận thấy là nếu tồn tại nhiều vị trí $j$ sao cho $b_j > a_i$ thì việc lựa chọn lung tung hay chọn $j$ **lớn** đồng nghĩa với việc **sự tối ưu** sẽ bị mất đi, khiến cho những giá trị $a_{i + 1}, a_{i + 2}, ..., a_n$ có thể sẽ sử dụng nhiều tòa tháp hơn. Vì vậy nếu tồn tại thì ta sẽ chọn vị trí $j$ nhỏ nhất để **ít ảnh hưởng** nhất vào đáp án cho các khối lập phương $a_{i + 1}, a_{i + 2}, ..., a_n$.
- Độ phức tạp : $O(n \log n)$.
:::
:::spoiler **Cài đặt**

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n;
    cin >> n;
    
    int a[n + 1];
    for(int i = 1; i <= n; ++i) cin >> a[i];

    vector<int> b;
    for(int i = 1; i <= n; ++i)
    {
        if(b.empty() or b.back() <= a[i]) b.push_back(a[i]);
        else
        {
            int position = upper_bound(b.begin(), b.end(), a[i]) - b.begin();
            b[position] = a[i];
        }
    }

    cout << (int)b.size();
    return 0;
}

:::
# WAVIO (Không có judge)
## Đề bài
- Cho dãy số nguyên gồm $n$ số nguyên $a_1, a_2, a_3, ..., a_n$. Một dãy con $b_1, b_2, b_3, ..., b_k$ của dãy $a$ được gọi là **gợn sóng** khi tồn tại vị trí $m$ sao cho $b_1 < b_2 < b_3 < ... < b_m > b_{m + 1} > b_{m + 2} > ... > b_k$. Tìm dãy **gợn sóng** có đồ dài lớn nhất là dãy con (có thể không liên tiếp) của dãy $a$.
### Input
- Dòng đầu gồm số nguyên dương $n$ ($n \leq 10^3$).
- Dòng tiếp theo gồm $n$ số nguyên : $a_1, a_2, a_3, ..., a_n$ ($-10^9 \leq a_i \leq 10^9$).

### Output
- Gồm $1$ số nguyên dương duy nhất là dãy **gợn sóng** dài nhất.
### Sample Input

6
2 1 3 2 5 3 

### Sample Output

4

### Giải thích
- Dãy **gợn sóng** dài nhất có độ dài $4$ là $1 \ 3 \ 5 \ 3$, một dãy khác có thể là $2 \ 3 \ 5 \ 3$.
## Lời giải
:::spoiler **Ý tưởng**
Gọi :
- $f_i$ là dãy con tăng dài nhất khi xét từ $1$ đến $i$ sao cho phần tử cuối cùng kết thúc tại $i$.
- $g_i$ là dãy con tăng dài nhất khi xét từ $n$ trở về $i$ sao cho phần tử cuối cùng kết thúc tại $i$.
- Nếu điểm $m$ đặt tại $i$ thì đáp án sẽ là $f_i + g_i - 1$ ($-1$ vì lặp lại vị trí $i$ $2$ lần).

Tới đây ta xử lý $2$ bài toán con một cách độc lập vói độ phức tạp $O(n^2)$.
:::
:::spoiler **Cài đặt**

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n;
    cin >> n;
    
    int a[n + 1];
    for (int i = 1; i <= n; ++i) cin >> a[i];
    
    int f[n + 1];
    for (int i = 1; i <= n; ++i)
    {
        int mx = 0;
        for(int j = 1; j < i; ++j)
            if(a[j] < a[i]) mx = max(mx, f[j]);
        f[i] = mx + 1;
    }
    
    int g[n + 1];
    for(int i = n; i >= 1; --i)
    {
        int mx = 0;
        for(int j = i + 1; j <= n; ++j)
            if(a[j] < a[i]) mx = max(mx, g[j]);
        g[i] = mx + 1;
    }

    int ans = 0;
    for(int i = 1; i <= n; ++i)
        ans = max(ans, f[i] + g[i] - 1);
    
    cout << ans;
    return 0;
}

:::