# Quy hoạch động :: Part 2
##### **Writer**: Nguyễn Hữu Phúc
##### **Reviewer**: zeena (i2225 PTNK)

* Ở chương trước chúng ta đã biết tới cách DP kiểu Fibonacci, cũng là cách đơn giản nhất trong quy hoạch động, vậy hôm nay ta sẽ đến với một kiểu DP mới, DP LIS.

Các kiến thức cần biết trước khi vào chương này:

* [Segment Tree :: Part 1](https://hackmd.io/@Phucc/BkEn6QZq3)
* [Quy hoạch động :: Part 1](/ktThVL_-SEClvahcO2VT7w)

Ok, tới đây nếu bạn nào chưa đọc 2 cái trên thì quay lại tham khảo còn chúng ta bắt đầu nhé !

----
### I. LIS Cơ bản
>**Bài toán:** *Cho một dãy $a$ gồm $n$ phần tử được đánh số từ $1$ tới $n$, hãy tìm tập con **dài nhất** của $a$ sao cho các phần tử trong tập con không giảm, với $n\leq 10^3$*.

Ở đây chúng ta có thể hiểu, một tập con của $a$ chính là một tập hợp các phần tử sao cho có thể tạo ra bằng cách xóa đi một số phần tử trong $a$ và giữ nguyên thứ tự các phần tử còn lại.

Từ đó, ta có thể rút ra nhận xét, ở một vị trí bất kì, chúng ta chỉ cần tối ưu độ dài tới nó bằng cách xét các vị trí trước nó (vì tập con thì giữ nguyên thứ tự) mà nhỏ hơn nó để tối ưu, cụ thể ta có công thức:

$dp_i=$ $\max\limits_{j = 1, A_j<A_i}^{i-1} {(dp_j+1)}$

Lưu ý nhỏ là để chính xác, ta cần đặt $dp_{i, (1\leq i\leq n)} = 1$ vì chính mỗi phần tử cũng chính là một tập con tăng.

Sau đây là code mẫu với độ phức tạp $O(n^2)$, các bạn có thể thử sức trước sau đó xem code mẫu này.

dp[n + 1];
for i in range 1 : n dp[i] = 1;
for i in range 1 : n
    for j in range 1 : i - 1
        if (a[i] >= a[j]) dp[i] = max(dp[i], dp[j] + 1);
print(*max_element(dp));

### II. LIS tối ưu
#### 1. Hướng giải
Chúng ta đã giải được bài toán này với $O(n^2)$, nhưng câu hỏi đặt ra là, nếu như cho một mảng với $n\leq 10^6$ và $a_{i, (1\leq i\leq n)}\leq 10^6$ thì ta có thể giải được không ?

Đáp án là có, chúng ta có hai thuật toán sau đây để giải bài toán này:

* Thuật toán tham lam với độ phức tạp $O(n$ $log(n))$
* Thuật toán quy hoạch động $+$ cấu trúc dữ liệu cây với độ phức tạp $O(n$ $log (n))$ như hằng số cao hơn

Về cơ bản, nếu gặp bài toán này thì phần lớn sẽ sử dụng thuật tham lam, nhưng nếu gặp các biến thể, thuật tham lam sẽ chết ngắc, do vậy, mình sẽ chỉ cách dùng cây, còn tham lam chỉ nêu code mẫu.

Code mẫu tham lam như sau:

const int INF = 1e9 + 1;
vector<int> b(n + 1, INF);
int ans = 0;
for i in range 1 : n 
    int k = upper_bound(b.begin(), b.end(), a[i]) - b.begin();
    ans = max(ans, k);
    b[k] = a[i];
print(ans);

#### 2. Ứng dụng cấu trúc dữ liệu trong giải bài toán LIS
Giờ quay lại với vấn đề chính, chúng ta sẽ sử dụng cấu trúc dữ liệu vào bài toán này như thế nào. Quay lại với nhận xét ban đầu, với mỗi phần tử, ta cần tìm phần tử trước nó nhỏ hơn nó có giá trị quy hoạch động lớn nhất.

Nói cách khác, nếu tồn tại $j$ sao cho $1 \le j < i$ và $A_j<A_i$ thì $dp_i = dp_j +1$, và ta muốn tìm $dp_j + 1$ lớn nhất

Chúng ta để ý rằng, $1\leq a_i\leq 10^6$ cho nên ta hoàn toàn có thể quản lí giá trị $dp$ của mỗi loại phần tử riêng biệt trong một mảng, từ đó ta thấy nhận xét như sau:

*Với mỗi phần tử $i$, ta tìm trong khoảng từ $1$ tới $a_i -1$ xem cái nào có giá trị quy hoạch động lớn nhất hiện tại, gọi biến $tmp$ chính là giá trị đó, update lại giá trị quy hoạch động của $a_i$ thành $tmp + 1$ rồi update trên cây, lí do là vì **với mỗi loại phần tử thì phần tử đứng sau cùng sẽ có giá trị quy hoạch động lớn nhất**, phần chứng minh mình xin để bạn đọc thử sức*.

Lưu ý, với cây lưu dữ liệu, các bạn có thể sử dụng *Fenwick Tree* hoặc *Segment Tree* tùy vào sở thích. Nhưng mình khuyên nên dùng *Fenwick Tree* vì nó dễ cài đặt hơn, code mẫu bài này như sau:

Tree tree; // Tree có thể hiểu là Segment Tree hoặc Fenwick Tree
for i in range 1 : n
    tree.upd(a[i], 1);
for i in range 1 : n
    int tmp = tree.qry(1, a[i]);
    tree.upd(a[i], tmp + 1);
print(tree.qry(1, 1e6));

### III. Các bài toán dạng LIS và hướng giải

Okay, tương tự chúng ta có bài [FOOLLIS](https://oj.vnoi.info/problem/fc146_foollis) cũng có thuật toán tương tự như vậy, chỉ đổi lại một chút là truy vấn lấy $tmp$ chỉ trong khoảng $a_i - k : a_i$, với bài toán này mình xin được để bạn đọc suy nghĩ.

Chúng ta sẽ đến với một bài khác phải đưa ra nhận xét và dùng não nhiều hơn: [Codeforces 1860C](https://codeforces.com/contest/1860/problem/C), tóm tắt đề của bài toán như sau:

> *Cho một hoán vị $p$ có độ lớn $n$ (một hoán vị có độ lớn $n$ là một tập hợp chỉ gồm các số từ $1$ tới $n$ và không có số nào trùng lặp nhau).*
>
>*Alice và Bob cùng chơi một trò chơi như sau:*
>
>*Đầu tiên, Alice chọn một phần tử $i$ và đặt một con chip lên đó (chip ở đây không nêu rõ là kiểu snack hay là kiểu con chip nhưng mình sẽ nói là con chip), lượt tiếp theo của Bob, anh ấy cần di chuyển con chip tới một phần tử $j$ sao cho $j < i$ và $p_j < p_i$, các bước tiếp sau đó Alice và Bob vẫn làm như vậy cho tới khi không thể di chuyển con chip thêm nữa, người đầu tiên không di chuyển được con chip là người thắng.*
>
>*Gọi một vị trí là đẹp nếu như sau khi Alice đặt con chip lên đó thì bất luận Bob đi như thế nào, phần thắng cũng thuộc về Alice, hãy đếm số vị trí được coi là đẹp*

Trước khi xem lời giải, bạn đọc có thể suy nghĩ và thử submit code vào đường link trên.

:::spoiler Cách giải bài toán
Chúng ta có thể nhận ra rằng, vấn đề ở đây là Alice sẽ chọn một phần tử $i$ sao cho phía trước nó có các phần tử $j$ thỏa mãn yêu mà không tồn tại các phần tử $k$ thỏa mãn yêu cầu tương tự cho $j$.

Cụ thể một phần tử $i$ được gọi là đẹp nếu:

* $p_i > p_j, 1\leq j\leq i - 1$
* $min(p_k) > p_j, (1\leq k\leq j - 1)$

Tới đây ta có thể suy ra công thức một vị trí $i$ là đẹp nếu $dp_i = 2$. Phần code mình xin để lại cho các bạn đọc.
:::
### IV. Đoạn kết
Tới đây post này cũng khá dài rồi, mình xin kết thúc ở đây, hẹn các bạn vào post sau - ***Quy hoạch động :: Part 3*** với sự xuất hiện của ***DP Knapsack và những kĩ thuật tối ưu hiệu quả nhất***.

### V. Bài tập tham khảo:

> [LIS EASY MODE](https://oj.vnoi.info/problem/liq)
> [LIS HARD MODE](https://oj.vnoi.info/problem/lis)
> [FOOLLIS](https://oj.vnoi.info/problem/fc146_foollis)