<button style="text-align:center; font-size:30px; color:none; background:none; border:none; padding:0; position:relative; left:38.5%;">
\(\color{#ff0000}{\text{Spoiler Alert}_{{}_{{}^{{}^{v2.9}}}}}\)
</button>

<button style="text-align:center; font-size:30px; color:none; background:none; border:none; padding:0; position:relative; left:38.5%;">
\(\color{orange}{\text{Mục lục}}\)
</button>

\(\color{#300000}{\text{1. Hint <Cày trâu>}}\)

• \(\color{#903030}{\text{<Ý tưởng>}}\) Thử từng dãy có thể, và kiểm tra nếu nó là dãy tăng thì cập nhật biến đếm

\(\color{#c01515}{\text{1. Approach <Cày trâu>}}\)

• \(\color{#f03030}{\text{<Cày trâu>}}\) Gọi \(mask = x_0 \times 2^0 + x_1 \times 2^1 + \dots + x_{n - 1} \times 2^{n-1}\) là trạng thái ta đang xét, với \(x_i = 1\) là chọn phần tử \(a_i\) và \(x_i = 0\) là không chọn. Tập \(S\) gồm các \(a_i\) với \(x_i = 1\) là một dãy con của mảng \(A[]\)

Gọi \(cnt\) là số phần tử của dãy tăng hiện tại, \(pre\) là số cuối cùng được chọn, khởi tạo là \(pre = 0\) (miễn là \(pre < min(A[])\))

Khi xét tới phần tử thứ \(i\) có \(x_i = 1\), đặt \(cur = a_i\). Nếu \(cur > pre\) thì ta lấy \(cur\) vào mảng nên đặt \(pre = cur\) và tăng biến đếm. Không thì ngừng vòng lặp vì nó không còn là dãy tăng

• \(\color{#f03030}{\text{<Phân tích độ phức tạp>}}\) \(\Theta(2^n \times n)\)

Có \(2^n\) dãy con \(S\), hay \(2^n\) trạng thái cho \(mask\)

Mỗi lần kiểm tra mất \(O(n)\)

Cập nhật mất \(O(1)\)

\(\color{#009933}{\text{1. Code tham khảo }}\): Bitmasking, Cày trâu

\(^{^{\color{#7f5f3f}{\text{Complexity : }} O(2^n \times n)\ \color{#7f5f3f}{\text{time}}\ ||\ O(n)\ \color{#7f5f3f}{\text{memory}}}}\)

int main()
{
    int n;
    cin >> n;

    vector<int> a(n);
    for (int &x : a) cin >> x;

    int res = 0;
    int lim = 1 << n;
    for (int mask = 0; mask < lim; ++mask)
    {
        int cnt = 0;
        int pre = 0;
        for (int i = 0; i < n; ++i)
        {
            if ((mask >> i) & 1)
            {
                int cur = a[i];
                if (pre < cur)
                {
                    pre = cur;
                    cnt++;
                }
                else break;
            }
        }

        maximize(res, cnt);
    }

    cout << res;
}

\(\color{#300000}{\text{2. Hint <Quy hoạch động>}}\)

• \(\color{#903030}{\text{Mảng quy hoạch động: }}\) Gọi \(f[i]\) là dãy tăng dài nhất của đoạn \([0..i]\).

Giả sử \(f_{-1}\) là một dãy rỗng

Gán \(f_i\) là dãy con \(f_j (j < i)\) có độ dài lớn nhất với phần tử cuối nhỏ hơn \(a_i\) và thêm phần tử \(a_i\) vào

Kết quả bài toán là độ dài dãy dài nhất

• \(\color{#903030}{\text{Nhận xét 1: }}\) Thuật trên đã đi đúng hướng, nhưng mà vì ta chỉ cần tìm độ dài dãy tăng dài nhất. Nên ta không cần lưu cả mảng mà chỉ xét \(f_n\) là độ dài dãy tăng dài nhất trong đoạn \([0..n)\)

Ý tưởng tương tự như trên. Nhưng thay vì phép hợp, ta tính \(f_i = f_j + 1\) đại diện cho việc thêm \(a_i\) thì độ dài tăng thêm 1

• \(\color{#903030}{\text{Nhận xét 2: }}\) Phần tử cuối của mảng \(f_n\) bất kì theo cách trên là \(a_n\), nên ta không cần lưu phần tử cuối làm gì.

\(\color{#c01515}{\text{2a. Approach <Quy hoạch động>}}\)

• \(\color{#f03030}{\text{Công thức quy hoạch động: }}\)

Khởi tạo thì một phàn tử cũng là một dãy tăng độ dài \(1\) nên \(f[i] = \{a_i\}\ \forall i \in [0, n)\)

Duyệt \(j \in [0, i)\) tìm dãy \(f_j\) có \(|f_j|\) lớn nhất mà phần tử cuối \(f_j\) nhỏ hơn \(a_i\). Đặt \(f_i = f_j \cup \{a_i\}\)

Kết quả bài toán là \(res = max(|f_i|), i \in [0, n)\)

• \(\color{#f03030}{\text{Phân tích độ phức tạp: }}\) \(O(n^3)\)

Mất \(O(n)\) để tìm \(f_j\) có \(|f_j|\) lớn nhất

Mất \(O(n)\) để gán \(f_i = f_j \cup \{a_i\}\)

Mất \(O(n)\) để tính cả mảng \(f[]\)

\(\color{#c01515}{\text{2b. Approach <Quy hoạch động>}}\)

• \(\color{#f03030}{\text{Công thức quy hoạch động: }}\)

Khởi tạo thì một phàn tử cũng là một dãy tăng độ dài \(1\) nên \(f[i] = 1 \forall i \in [0, n)\)

Tính \(f_i = max(f_j) + 1\) thỏa \(a_j < a_i\)

Kết quả bài toán là \(res = max(f_i), i \in [0, n)\)

• \(\color{#f03030}{\text{Phân tích độ phức tạp: }}\) \(O(n^2)\)

Mất \(O(n)\) để tìm \(f_j\) có \(|f_j|\) lớn nhất

Mất \(O(1)\) để gán \(f_i = f_j + 1\)

Mất \(O(n)\) để tính cả mảng \(f[]\)

\(\color{#009933}{\text{2a. Code tham khảo }}\): Quy hoạch động

\(^{^{\color{#7f5f3f}{\text{Complexity : }} O(n^3)\ \color{#7f5f3f}{\text{time}}\ ||\ O(n)\ \color{#7f5f3f}{\text{memory}}}}\)

int main()
{
    int n;
    cin >> n;

    vector<int> a(n);
    for (int &x : a) cin >> x;

    vector<int> f[n];
    for (int i = 0; i < n; ++i)
    {
        f[i] = {a[i]};

        int j = -1, l = 0;
        for (int p = 0; p < i; ++p)
        {
            if (f[p].back() < a[i])
            {
                if (l < f[p].size())
                {
                    l = f[p].size();
                    j = p;   
                }
            }
        }

        if (j > -1)
        {
            f[i] = f[j];
            f[i].push_back(a[i]);
        }
    }

    int res = 0;
    for (int i = 0; i < n; ++i)
        if (res < f[i].size())
            res = f[i].size();

    cout << res;
    return 0;
}

\(\color{#009933}{\text{2b. Code tham khảo }}\): Quy hoạch động

\(^{^{\color{#7f5f3f}{\text{Complexity : }} O(n^2)\ \color{#7f5f3f}{\text{time}}\ ||\ O(n)\ \color{#7f5f3f}{\text{memory}}}}\)

int main()
{
    int n;
    cin >> n;

    vector<int> a(n);
    for (int &x : a) cin >> x;

    vector<int> f(n, 1);
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < i; ++j)
            if (a[i] > a[j])
                maximize(f[i], f[j] + 1);

    int res = *max_element(f.begin(), f.end());
    cout << res;
    return 0;
}

\(\color{#300000}{\text{3. Hint <Đảo nhãn quy hoạch động>}}\)

• \(\color{#903030}{\text{Mảng quy hoạch động: }}\) Gọi \(f_n\) là dãy tăng dài nhất có độ dài \(n\)

• \(\color{#903030}{\text{Nhận xét 1: }}\) Nếu thêm một phần tử \(a_i\) vào một dãy tăng độ dài \(len\) bất kì có phần tử cuối bé hơn \(a_i\) ta tạo được dãy tăng mới có độ dài \(len + 1\)

• \(\color{#903030}{\text{Tư tưởng 1: }}\) Khi xét tới phần tử \(a_i\), ta duyệt qua lần lượt các \(f_j\ (j < i)\) và nếu phần tử cuối của dãy \(f_j\) nhỏ hơn thì ta chèn \(a_i\) vào và tạo được dãy mới có độ dài \(j + 1\). Độ phức tạp \(O(n^4)\)

• \(\color{#903030}{\text{Nhận xét 2: }}\) Trong tất cả dãy tăng dài nhất có cùng độ dài. Ta nên chọn dãy có phần tử cuối nhỏ nhất để chèn thêm, nhưng ta không cần cập nhật dãy đó cho tất cả dãy có độ dài lớn hơn

• \(\color{#903030}{\text{Tư tưởng 2: }}\) Khi xét tới phần tử \(a_i\), ta duyệt qua lần lượt các \(f_j\ (j < i)\) và nếu phần tử cuối của dãy \(f_j\) nhỏ hơn thì ta chèn \(a_i\) vào và tạo được dãy mới có độ dài \(j + 1\). Nếu tồn tại dãy tăng độ dài \(j + 1\) khác, ta sẽ bỏ dãy có phần tử cuối lớn hơn. Độ phức tạp \(O(n^3)\)

• \(\color{#903030}{\text{Nhận xét 3: }}\) Ta không cần quan tâm tới dãy, mà chỉ quan tâm tới độ dài, nhưng lưu ý lúc này phần tử cuối \(f_j\) không phải là \(a_j\). Nên ta sẽ đặt lại mảng quy hoạch động \(f_n\) là phần tử cuối dãy tăng dài nhất có độ dài \(n\)

• \(\color{#903030}{\text{Tư tưởng 3: }}\) Tương tự như tư tưởng 2, nhưng ta chỉ kiểm tra phần tử cuối thay vì tạo dãy mới chọn dãy có tính trội tốt và loại bỏ dãy có tính xấu. Độ phức tạp \(O(n^2)\)

• \(\color{#903030}{\text{Nhận xét 4: }}\) Dãy tạo bởi các phần tử cuối của mảng quy hoạch động cũng là dãy tăng dài nhất. Nên ta có thể chặt nhị phân trên mảng tăng dần tìm vị trí nhỏ nhất lớn hơn bằng \(a_i\) để thay mới. Việc thay phần tử cuối cùng này xem tạo mới - nhận tốt - loại xấu như tư tưởng 3, nhưng vì có phần chung \([0, i)\) nên ta chỉ cần lưu giá trị cuối.

• \(\color{#903030}{\text{Tư tưởng 4: }}\) Gọi mảng \(b[]\) là một dãy tăng tốt đang xét, mảng \(f[]\) với \(f_p\) là vị trí nhỏ nhất có \(b_p < a_i\). Và ta thay giá trị này bằng \(a_i\) để được dãy mới tốt hơn. Độ phức tạp \(O(n\ log\ n)\)

• \(\color{#903030}{\text{Lưu ý: }}\) Mảng \(b[]\) không phải dãy tăng dài nhất cùng tìm nhưng có độ dài bằng dãy dài nhất ấy, muốn truy vết dãy phải dùng cách khác

\(\color{#c01515}{\text{3. Approach}}\)

• \(\color{#f03030}{\text{Công thức quy hoạch động: }}\)

Khởi tạo \(res = 0\) là kết quả, \(b[i] = +oo\ \forall i \in [0, n)\) là dãy tăng dài nhất (không tính các phần tử có giá trị \(+oo\))

Khi xét tới \(i\), \(f[i] = lower_bound(b[], a[i])\), là tìm vị trí nhỏ nhất mà gặp phần tử xấu

Cập nhật kết quả, \(res = max(res, f[i] + 1)\), vì vị trí mảng + 1 cũng là độ dài của mảng được thêm phần tử \(a_i\) đang xét

Cập nhật giá trị, \(b[f[i]] = a[i]\)

\(\color{#009933}{\text{3a. Code tham khảo }}\): Quy hoạch động, Đảo nhãn Quy hoạch động, chặt nhị phân, Giải trực tiếp

\(^{^{\color{#7f5f3f}{\text{Complexity : }} O(n\ log\ LIS)\ \color{#7f5f3f}{\text{time}}\ ||\ O(n)\ \color{#7f5f3f}{\text{memory}}}}\)

const int INF = 1e9;
int main()
{
    int n;
    cin >> n;

    int res = 0;
    vector<int> a(n), f(n), b(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        b[i] = +INF;
        f[i] = lower_bound(b.begin(), b.begin() + res + 1, a[i]) - b.begin();
        res = max(res, f[i] + 1);
        b[f[i]] = a[i];
    }

    cout << res;
    return 0;
}

\(\color{#009933}{\text{3b. Code tham khảo }}\): Quy hoạch động, Đảo nhãn Quy hoạch động, chặt nhị phân, Giải trực tiếp

\(^{^{\color{#7f5f3f}{\text{Complexity : }} O(n\ log\ LIS)\ \color{#7f5f3f}{\text{time}}\ ||\ O(n)\ \color{#7f5f3f}{\text{memory}}}}\)

int main()
{
    int n;
    cin >> n;

    vector<int> a;
    for (int i = 0; i < n; ++i)
    {
        int x;
        cin >> x;

        vector<int>::iterator it;
        it = lower_bound(a.begin(), a.end(), x);
        if (it != a.end()) *it = x;
        else a.push_back(x);
    }

    cout << a.size();
}

\(\color{#7f5f3f}{\text{3. Special::Truy vết}}\)

• Duyệt ngược mảng về, nếu tại vị trí \(p\) lớn nhất có \(f_p + 1 = res\) thì giảm \(res\) và thêm phần tử \(a_p\) vào mảng. Vì ta duyệt ngược nên lát phải đảo ngược mảng

\(\color{#009933}{\text{3. Code bonus }}\): Truy vết

\(^{^{\color{#7f5f3f}{\text{Complexity : }} O(n)\ \color{#7f5f3f}{\text{time}}\ ||\ O(n)\ \color{#7f5f3f}{\text{memory}}}}\)

void lis(const vector<int> &f, const vector<int> &b, vector<int> &LIS)
{
    int res = *max_element(f.begin(), f.end()) + 1; /// max(f[i] + 1);

    for (int p = b.size(); p-->0; )
    {
        if (res == f[p] + 1)
        {
            res--;
            LIS.push_back(a[p]);
        }
    }

    reverse(all(LIS));
}

\(\color{#300000}{\text{4. Hint <Online Solving> or <Deep-Optimization>}}\)

• \(\color{#903030}{\text{Gợi ý: }}\) Dãy tăng dài nhất có thể giải trong \(O(n\ log(log\ LIS))\) bằng cách chia thành từng đoạn nhỏ và xử lí dần rồi hợp lại. Trong đó tối ưu bằng Radix Sort và cây van Emde Boas

• \(\color{#903030}{\text{Gợi ý: }}\) Dãy tăng dài nhất có thể giải trực tiếp trong \(O(n\ log(log\ n))\)

\(\color{#c01515}{\text{4. Approach <Optimization>}}\)

• \(\color{#f03030}{\text{Tài liệu: }}\) Bạn đọc tham khảo tại đây