[TOC] # Lời nói đầu Quy hoạch động trên thành phần liên thông hay DP Connected Components là một kỹ thuật không phổ biến với đại đa số cp-er, mình thấy những tài liệu viết về kỹ thuật này không nhiều, cũng không có chi tiết nên mình đã mất khá nhiều thời gian để hiểu kỹ thuật này, nên mình sẽ truyền tải một cách hiểu đối với quy hoạch động trên thành phần liên thông, cách kỹ thuật đặt trạng thái tương đối lạ này thông qua bài viết này. Trong bài viết nếu có những phần nào chưa ổn xin mọi người góp ý để mình có cơ hội hoàn thiện bài viết. **Kiến thức cần thiết : Quy hoạch động, Quy hoạch động đảo nhãn.** Quy hoạch động trên thành phần liên thông là một dạng bài xử lý các bài toán trên hoán vị, nhiều hoán vị hay tất cả hoán vị thỏa mãn một đặc trưng nào đó của yêu cầu đề bài. Thường nó có một số đặc điểm sau : - Đếm số hoán vị thỏa mãn một hay nhiều tính chất nào đó. - Xét tất cả hoán vị, tìm giá trị của hàm $f(p)$ lớn nhất hay nhỏ nhất với $p$ là một hoán vị nào đó. # Giới thiệu **Bài toán mở đầu :** Đếm số lượng hoán vị độ dài $N$ chia lấy phần dư cho $10^9 + 7$. Giới hạn $1 \leq N \leq 10^3$. Mới nhìn vô thì thông thường mọi người sẽ đều giải bằng tổ hợp, cụ thể là chỉ cần tìm giai thừa của $n$ là được. Nhưng thay vì giải bằng cách in ra giai thừa $n! =$ $1 \times 2 \times 3 \times ... \times n \bmod (10^9 + 7)$ thì chúng ta sẽ giải bài toán theo một hướng khác để dễ hình dung cách hoạt động của kỹ thuật này trong các bài toán xử lý hoán vị. ## Định nghĩa thành phần liên thông trong một hoán vị Trước hết thì tại sao **thành phần liên thông** lại liên quan tới hoán vị ? Giả sử ta có một dãy hoán vị $p$ độ dài $N$, nhưng ban đầu tất cả đều là những dấu $?$, ta sẽ lần lượt tìm cách điền các số từ $1$ tới $N$ lên những dấu $?$ đúng $1$ lần vào mỗi vị trí trong hoán vị hiện tại. > *Định nghĩa **thành phần liên thông** trong hoán vị chính là những vị trí ta đa điền bằng những giá trị lên các dấu $?$, khi đó những phần tử nào kề nhau và không bị tách rời bởi dấu $?$ sẽ được coi chung là thành phần liên thông. > Ví dụ với $N= 8$, và ta đã điền các số tự nhiên $1, 2, 3$ và một trong những cách điền : $$ ?1???32?? $$ Trường hợp này, để tiện biểu diễn, chúng ta sẽ sử dụng **tập hợp có thứ tự (ordered set).** Mô tả lại, ta sẽ định nghĩa tập hợp các thành phần liên thông tức là các giá trị kề nhau không có dấu $?$. Trong ví dụ này, chúng ta có hai thành phần liên thông là $\{1\}$ và $\{3, 2\}$. Lưu ý một chút, tập hợp chúng ta đang xét sẽ có **tính thứ tự**. Nghĩa là $\{a, b\} \neq \{b, a\} \ (a \neq b)$ và $\{a, b\} \neq \{a, c\} \ (b \neq c)$. Ví dụ như ta đang chia các số tự nhiên từ $1$ đến $5$ thành : $\{ \{3, 2\}, \{5\}, \{1, 4\}\}$, chúng sẽ có dạng $???32??5??14$, hoặc là $??32?5???14?$ nhưng sẽ không có dạng $??325????14$ hay $3214??5???$. Ở đây $\{ \{3, 2\}, \{5\}, \{1, 4\}\}$ sẽ có $3$ thành phần liên thông. Với một hoán vị độ dài $N$ sẽ có đúng duy nhất $1$ thành phần liên thông, ví dụ như với một hoán vị độ dài $N = 5$ có thể là $\{ \{1, 3, 4, 2, 5\} \}$ hay $\{\{2, 3, 4, 5, 1\}\}$. ## Công thức quy hoạch động Đặt $f(i, j)$ là số lượng cách để điền các số tự nhiên $1, 2, ..., i$ vào hoán vị độ dài $N$ và trong đó có $j$ thành phần liên thông. Như vậy đáp án của ta sẽ là $f(N, 1)$ Truy hồi công thức : - Trường hợp 1 : Ta coi giá trị $i + 1$ là một thành phần liên thông phân biệt, lúc này ta có $j + 1$ ô trống giữa $j$ thành phần liên thông (tính luôn cả đầu và đuôi của hoán vị), ví dụ với : $$ \{\{x, y, z, w\}, \{a, b, c, d\} \} $$ - Ta có thể điền $i + 1$ giữa hai thành phần liên thông $\{x, y, z, w\}$ và $\{a, b, c, d\}$ hoặc nằm trước $\{x, y, z, w\}$ hoặc nằm sau $\{a, b, c, d\}$. - Trường hợp này ta có $j + 1$ cách chọn : $f(i + 1, j + 1) = f(i, j) \times (j + 1)$ - Trường hợp 2 : Ta sẽ đưa $i + 1$ vào đầu hoặc đuôi một thành phần liên thông đã có sẵn, ví dụ : $$ \{\{a, b, c, d\}, \{e, f, g\}, \{x, y, z\}\} $$ - Lúc này ta có thể đưa $i + 1$ vào hai đầu của $\{a, b, c, d\}, \{e, f, g\}$ hoặc $\{x, y, z\}$ thành $\{i + 1, a, b, c, d\}$ hay $\{x, y, z, i + 1\}$. - Trường hợp này ta có $2j$ cách chọn : $f(i + 1, j) = f(i, j) \times 2j$ - Trường hợp 3 : Ta sẽ dùng $i + 1$ là cầu nối giữa hai thành phần liên thông trong $j$ thành phần liên thông $$ \{\{a, b, c, d\}, \{e, f, g\}, \{x, y, z\}\} $$ - Ta có thể dùng $i + 1$ để nối $\{\{a, b, c, d\}$ với $\{e, f, g\}$, hoặc $\{e, f, g\}$ với $\{x, y, z\}$ thành $\{\{a, b, c, d, i + 1, e, f, g\}, \{x, y, z\} \}$ hoặc $\{ \{a, b, c, d\}, \{e, f, g, i + 1, x, y, z\} \}$. - Trường hợp này ta có $j - 1$ cách chọn : $f(i + 1, j - 1) = f(i, j) \times (j - 1)$ Độ phức tạp : $\text{O}(N^2)$. ```cpp #include "bits/stdc++.h" using namespace std; const int mod = 1e9 + 7; const int MAX = 1e3 + 5; void add(int& a, int b){ a += b; if(a >= mod) a -= mod; } int mul(int a, int b){ return 1LL * a * b % mod; } int n; int f[MAX][MAX]; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cin >> n; f[0][0] = 1; for(int i = 0; i < n; ++i){ for(int j = 0; j <= i; ++j){ //Tạo thêm một thành phần liên thông add(f[i + 1][j + 1], mul(j + 1, f[i][j])); //Thêm vào đầu hoặc đuôi một trong j thành phần liên thông add(f[i + 1][j], mul(2 * j, f[i][j])); //Nối hai thành phần liên thông bằng i + 1 if(j > 0) add(f[i + 1][j - 1], mul(j - 1, f[i][j])); } } cout << f[n][1] << '\n'; return 0; } ``` **Mở rộng : hãy in ra $f(i,j )$ và xét $f(i, i - j + 1)$.** # Chứng minh tính đúng đắn Ta phải chứng minh hai điều là mọi hoán vị đều được **tính đúng một lần** và trong hàm quy hoạch động các hoán vị cũng được đếm **không trùng nhau**. ## Chứng minh mọi hoán vị đều được đếm không trùng nhau Xét ví dụ sau : $$ \{\{A, B,C, D\}, \{E, F, G\}, \{H, I, J\}\} $$ Cấu hình này ta chỉ vừa điền $10$ phần tử và có $3$ thành phần liên thông, và nó sẽ đóng góp vào $f(10, 3)$ trong công thức quy hoạch động, khi ta thêm $K$ vào ta sẽ xem có sự **trùng lặp** nào trong cách đếm của ta hay không. Trên thuật toán chúng ta có $3$ trường hợp chuyển trạng thái là : 1. Thêm một thành phần liên thông mới 2. Thêm giá trị mới vào đầu hoặc đuôi của những thành phần liên thông đã có sẵn 3. Nối hai thành phần liên thông. Trường hợp $1$ : Ta đưa $K$ trở thành một thành phần liên thông mới, lúc này không mất tính tổng quát, ta coi nó là hoán vị của $\{\{A, B,C, D\}, \{E, F, G\}, \{H, I, J\}, \{K\}\}$ do trường hợp này ta sử dụng nhiều thành phần liên thông hơn nên chắc chắn nó không thể giao với trường hợp $2$ hoặc $3$ được. Trường hợp $2$ và $3$ : - Trong trường hợp $2$ : Ta đặt $K$ là cầu nối giữa hai thành phần liên thông nào đó, giả sử trong một cách cấu hình ta dùng $K$ nối giữa $\{A, B, C, D\}$ và $\{E, F, G\}$, ta cũng coi nó như $\{\{A, B,C, D, K, E, F, G\}, \{H, I, J\}\}$. - Trường hợp $3$ : Ta đặt $K$ là đầu hoặc đuôi của một trong các thành phần liên thông hiện tại, giả sử ta đặt $K$ ở đuôi của $\{A, B, C, D\}$ thành $\{A, B, C, D, K\}$ tạo thành $\{\{A, B,C, D, K\}, \{E, F, G\}, \{H, I, J\}\}$ - Nếu trong cách đếm tại trường hợp $2$ ta có đặt $K$ ở đuôi của $\{A, B, C, D\}$ thành $\{A, B, C, D, K\}$ hay đầu của $\{E, F, G\}$ thành $\{K, E, F, G\}$ đi chăng nữa thì để hợp chúng lại, ta cũng tồn tại một giá trị $Z$ nào đó lúc ta điền vào để nối hai thành phần liên thông này ở một lúc nào đó tạo thành $\{A, B, C, D, K, Z, E, F, G\}$ hoặc $\{A, B, C, D, Z, K, E, F, G\}$ cũng không trùng nhau, nên cách đếm ở trường hợp $2$ không giao với cách đếm ở trường hợp $3$. - Từ đây ta có thể dùng quy nạp để chứng minh cho trường hợp tổng quát các hoán vị được tính đúng một lần do các cấu hình mới sinh ra không trùng nhau. ## Chứng minh với mọi hoán vị đều được tính đúng một lần Với trường hợp $N = 1$ thì hiển nhiên đúng. **Ghi chú** : Thuật toán của ta điền các giá trị lần lượt từ $1, 2, 3, ..., N$. Với trường hợp $N > 2$, xét quan hệ của mọi vị trí $i$ thỏa mãn $1 < i < N$ với hai phần tử liên kề nó, sẽ có $2^2 = 4$ trường hợp có thể xảy ra : - $p_{i - 1} < p_i < p_{i + 1}$ : Khi này tồn tại cấu hình này vì ta điền $p_{i - 1}$ trước, giữ nguyên $p_{i - 1}$ là đuôi của thành phần liên thông đó, sau đó điền $p_i$ vào đuôi thành phần liên thông chứa $p_{i - 1}$ rồi cũng giữ nguyên đuôi cho tới lần điền $p_{i + 1}$. - $p_{i - 1} < p_i > p_{i + 1}$ : Ta cũng sẽ giữ nguyên đuôi là $p_{i - 1}$ với thành phần liên thông chứa $p_{i - 1}$ và giữ nguyên đầu là $p_{i + 1}$ với thành phần liên thông chứa $p_{i + 1}$ rồi hợp hai thành phần liên thông khi tới lần điền $p_i$. - $p_{i - 1} > p_i < p_{i + 1}$ : Ta điền $p_i$ làm một thành phần liên thông mới và chỉ đứng một mình cho tới khi thăm $p_{i - 1}$ hoặc $p_{i + 1}$ trước, ta sẽ nối đầu đuôi của chúng trước hoặc sau tùy thuộc giá trị $p_{i - 1}, p_{i + 1}$ và vẫn tạo ra được cấu hình này. - $p_{i - 1} > p_i > p_{i + 1}$ : Tương tự với trường hợp $p_{i - 1} < p_i < p_{i + 1}$, ta sẽ giữ nguyên đầu là $p_{i + 1}$, điền $p_i$, giữ nguyên đầu và cuối cùng là điền $p_{i - 1}$. Đối với trường hợp $i = 1$ và $i = N$ thì cũng tương tự việc xét, giữ nguyên cho tới lượt điền để thỏa mãn được việc tạo ra các dấu $<, >$ tùy ý. Tới đây, ta nhận thấy rằng chỉ cần biết được **vị trí tương đối** của $p_i$ trong hoán vị, ta hoàn toàn có thể xây dựng hoán vị $p$ bằng $3$ thao tác đã đề cập trong hàm quy hoạch động. Ta chứng minh được rằng mọi hoán vị đều có thể được sinh ra từ hàm quy hoạch động. # Bài tập ví dụ Sau khi điểm qua những định nghĩa, chứng minh tính đúng đắn của kỹ thuật, mình sẽ sử dụng một số ký hiệu sau để thuận tiện cho việc giải thích, mô tả lời giải dễ hiểu hơn : - $???ABC??XYZ?? \rightleftharpoons \{\{A,B,C\}, \{X, Y, Z\}\}$ sẽ mô tả rằng một hoán vị đang được điền có dạng ví dụ như $???ABC??XYZ??$ có thể được mô tả bằng tập hợp $\{\{A,B,C\}, \{X, Y, Z\}\}$. - “TPLT” là viết tắt của thành phần liên thông. ## 1. CSES1075 Permutations II ### Đề bài Link đề bài : https://cses.fi/problemset/task/1075 **Tóm tắt đề bài :** Đếm số hoán vị độ dài $N$ sao cho không có hai phần tử liên tiếp nào có chênh lệch là $1$ (Tức là không tồn tại giá trị $i$ kề giá trị $i + 1$ trong hoán vị), chia lấy phần dư kết quả cho $10^9 + 7$ Giới hạn : $1 \leq N \leq 10^3$ ### Phân tích và lời giải Ta sẽ điền lần lượt các số tự nhiên từ $1$ tới $N$ vào hoán vị cũng như bài toán tính số hoán vị. Với cách điền này, ta chỉ cần quan tâm vị trí của $i$ trước đó ta điền ở đâu và khi điền tiếp $i + 1$, chỉ cần không điền kề $i$ là được. Gọi $f(i, j, k)$ là số cách để ta điền $1, 2, 3, ..., i$ vào hoán vị độ dài $N$ sao cho hình thành $j$ TPLT sao cho không có TPLT nào có hai phần tử liên tiếp nhau có chênh lệch là $1$, và $k$ mô tả : - $k = 0 :$ hiện tại $\{i\}$ đang là một TPLT **riêng biệt** **nằm ngoài cùng** (trái hoặc phải) của các TPLT, ví dụ : - Với $i = 7$, ta có $??7??24?35??1? \rightleftharpoons \{ \{7\}, \{2, 4\}, \{3, 5\}, \{1\} \}$ và $\{7\}$ là TPLT trái nhất trong $3$ TPLT. - $k = 1 :$ hiện tại $\{i\}$ cũng đang là một TPLT **riêng biệt** nhưng **không nằm ngoài cùng** của các TPLT, ví dụ : - Với $i = 5$, ta có $42??5??13?? \rightleftharpoons \{\{4, 2\}, \{5\}, \{1, 3\} \}$ và $\{5\}$ không phải một trong những TPLT nằm ở biên. - $k = 2 :$ hiện tại $i$ đang **nằm giữa trong một TPLT** và không có bất kỳ đầu mút nào của các TPLT bằng $i$, ví dụ : - Với $i = 6$, ta có $???465?13?2?? \rightleftharpoons \{ \{4, 6, 5\}, \{1, 3\}, \{2\}\}$ và $6$ nằm giữa TPLT $\{4, 6, 5\}$ và không còn có đầu mút nào khác bằng $6$. - $k = 3 :$ hiện tại $i$ đang là **đầu / đuôi** của một trong $j$ TPLT và TPLT chứa $i$ **nằm ngoài cùng với $i$ hướng ra ngoài**, ví dụ : - Với $i = 8$, ta có $?475??62?1??38?? \rightleftharpoons \{\{4, 7, 5\}, \{6, 2\}, \{3, 8\}\}$ và $8$ đang nằm ngoài cùng bên phải và nó cũng hướng ra bên phải, cũng tương tự với trường hợp $??8642??13?57?? \rightleftharpoons \{\{8, 6, 4, 2\}, \{1, 3\}, \{5, 7\}\}$ khi $8$ nằm ngoài cùng bên trái và nó cũng hướng ra bên trái. - $k = 4 :$ hiện tại $i$ cũng đang là **đầu / đuôi** của một trong $j$ TPLT nhưng TPLT chứa $i$ không nằm ngoài cùng hoặc $i$ không hướng ra ngoài, ví dụ : - Với $i = 9$, ta có $??479??825??31?? \rightleftharpoons \{\{4, 7, 9\}, \{8, 2, 5\}, \{3, 1\}\}$ và $9$ nằm ở đuôi của TPLT $\{4, 7, 9\}$ nhưng bên phải TPLT này tồn tại TPLT $\{8, 2, 5\}$ nên nó không hướng ra ngoài. Đáp án sẽ là $\sum_{k = 0}^4 f(N, 1, k)$. Giờ đến với bước chuyển trạng thái từ $f(i, j, k)$, mình sẽ lấy ví dụ với $k = 0, k = 1$ và với $k \geq 2$ mình sẽ **nhường lại cho bạn đọc**. Trước tiên, chúng ta sẽ có $5$ thao tác để chuyển trạng thái khi đã điền $1, 2, 3, ..., i$ cùng với ví dụ : - Tạo TPLT mới $\{i + 1\}$ nằm **ở ngoài cùng** (trái hoặc phải), ví dụ : $\{i + 1\} \{...\} \{...\}$ - Tạo TPLT mới $\{i + 1\}$ nằm **không nằm ở ngoài cùng**, ví dụ : $\{...\} \{i+ 1\} \{...\}$ - Gán $i + 1$ nằm ở đầu / đuôi với TPLT ngoài cùng (nếu TPLT trái nhất thì là đầu, nếu TPLT phải nhất thì là đuôi), ví dụ : $\{i + 1, ...\} \{...\} \{...\}$ - Gán $i + 1$ nằm ở đầu / đuôi với những TPLT hướng ra TPLT kề TPLT hiện tại, ví dụ : $\{..., i + 1\} \{...\} \{...\}$ - Nối hai TPLT bằng $i + 1$, ví dụ : $\{...\} \{..., i + 1, ...\}, \{...\}$ Chuyển trạng thái $k = 0$ : (Có dạng $\{i\}\{...\}\{...\}$ ) - Thao tác $1 : f(i + 1, j + 1,0) = f(i, j, 0) \times2$ (Thêm làm TPLT ngoài cùng trái hoặc phải) - Thao tác $2 : f(i + 1, j + 1, 1) = f(i, j, 0) \times (j - 1)$ (Thêm giữa $j - 1$ khe trong $j$ TPLT) - Thao tác $3 : f(i + 1, j + 1, 3) = \begin{cases} 0, & \text{Khi j = 1} \\ f(i, j, 0), & \text{Khi j > 1} \end{cases}$ (Không thể chọn nếu chỉ còn $1$ TPLT) - Thao tác $4 : f(i + 1, j, 4) = f(i, j, 0) \times (2 \times(j - 1) - 1)$ (Không thể chọn TPLT ngoài cùng của $\{i\}$) - Thao tác $5 : f(i + 1, j - 1, 2) = f(i, j, 0) \times (j - 2)$ (Không thể nối giữa TPLT ngoài cùng với TPLT kề nó) Chuyển trạng thái $k = 1$ : (Có dạng $\{...\} \{i\} \{...\}$) - Thao tác $1 : f(i + 1, j + 1,0) = f(i, j, 0) \times2$ (Tương tự trường hợp $k = 0$). - Thao tác $2 : f(i + 1, j + 1, 1) = f(i, j, 0) \times (j - 1)$ (Tương tự trường hợp $k = 0$). - Thao tác $3 : f(i + 1, j, 3) = f(i, j, 1) \times 2$ (Không ảnh hưởng tới việc chọn các TPLT hai biên). - Thao tác $4 : f(i + 1, j, 4) = f(i, j, 1) \times (2 \times(j - 2))$ (Không được chọn hai đầu của TPLT $\{i\}$) - Thao tác $5 : f(i + 1, j - 1, 2) = f(i, j, 1) \times (j - 3)$ (Có $2$ khe giữa hai TPLT kề $\{i\}$ không được chọn) Các trường hợp còn lại độc giả tự nghĩ để hiểu hơn về kỹ thuật này nhé. Độ phức tạp $O(N^2)$ ```cpp #include <bits/stdc++.h> using namespace std; const int MAX = 1e3 + 5; const int mod = 1e9 + 7; int N, f[MAX][MAX][5]; void add(int& x, int y){ x += y; assert(y >= 0); if(x >= mod) x -= mod; } int mul(int x, int y){ assert(y >= 0); return 1ll * x * y % mod; } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cin >> N; f[1][1][0] = 1; for(int i = 1; i < N; ++i){ for(int j = 1; j <= i; ++j){ for(int k = 0; k < 5; ++k){ //Trường hợp tạo TPLT mới như nhau add(f[i + 1][j + 1][0], mul(f[i][j][k], 2)); add(f[i + 1][j + 1][1], mul(f[i][j][k], j - 1)); } ///f[i][j][0] : [i] [...] [...] [...] add(f[i + 1][j][3], (j > 1 ? f[i][j][0] : 0)); //thao tác 3 add(f[i + 1][j][4], mul(f[i][j][0], max(0, 2 * (j - 1) - 1))); //thao tác 4 add(f[i + 1][j - 1][2], mul(f[i][j][0], max(0, j - 2))); //thao tác 5 ///f[i][j][1] : [...] [...] [i] [...] [...] add(f[i + 1][j][3], mul(f[i][j][1], 2)); //thao tác 3 add(f[i + 1][j][4], mul(f[i][j][1], max(0, 2 * (j - 2)))); //thao tác 4 add(f[i + 1][j - 1][2], mul(f[i][j][1], max(0, j - 3))); //thao tác 5 ///f[i][j][2] : [...] [...i...] [...] [...] add(f[i + 1][j][3], mul(f[i][j][2], 2)); //thao tác 3 add(f[i + 1][j][4], mul(f[i][j][2], 2 * (j - 1))); //thao tác 4 add(f[i + 1][j - 1][2], mul(f[i][j][2], j - 1)); //thao tác 5 ///f[i][j][3] : [i...] [...] [...] [...] add(f[i + 1][j][3], f[i][j][3]); //thao tác 3 add(f[i + 1][j][4], mul(f[i][j][3], max(0, 2 * (j - 1)))); //thao tác 4 add(f[i + 1][j - 1][2], mul(f[i][j][3], j - 1)); //thao tác 3 ///f[i][j][4] : [...] [...i] [...] [...] add(f[i + 1][j][3], mul(f[i][j][4], 2)); ////thao tác 3 add(f[i + 1][j][4], mul(f[i][j][4], max(0, 2 * (j - 1) - 1))); //thao tác 4 add(f[i + 1][j - 1][2], mul(f[i][j][4], max(0, j - 2))); // thao tác 5 } } int ans = 0; add(ans, f[N][1][0]); add(ans, f[N][1][1]); add(ans, f[N][1][2]); add(ans, f[N][1][3]); add(ans, f[N][1][4]); cout << ans << '\n'; return 0; } ``` **Mở rộng :** Bài này thật ra còn có công thức tính $f(n)$ là số hoán vị độ dài $n$ thỏa mãn yêu cầu của bài toán trên OEIS (https://oeis.org/A002464.) với độ phức tạp $O(n)$. ## 2. Codeforces Global Round 14 E. Phoenix and Computers ### Đề bài Link đề bài : https://codeforces.com/contest/1515/problem/E **Tóm tắt đề bài :** Với một dãy bit độ dài $N \leq 400$ đánh số từ $1$ tới $N$ ban đầu tất cả đều bằng $0$, có hai cách để biến một bit $0$ thành một bit $1$ là : - Trực tiếp biến bit $i$ từ $0$ thành $1$ - Gián tiếp biến bit $i \ (2 \leq i \leq n - 1)$ từ $0$ thành $1$ bằng cách để bit $i - 1$ và bit $i + 1$ thành $1$ trước. Một bit đã được bật rồi thì không được **bật trực tiếp** lại. Đếm số dãy thao tác trực tiếp biến bit $s_i$ thành $1$ : $s_1, s_2, ..., s_k$ sao cho tất cả $N$ bit đều biến thành $1$. sau khi thực hiện. Hai dãy thao tác bật trực tiếp $a_1, a_2, ..., a_n$ và $b_1, b_2, ..., b_m$ được coi là khác nhau khi $n \neq m$ hoặc $\exists i, a_i \neq b_i$. In ra kết quả chia lấy phần dư cho $M$ . Giới hạn : $3 \leq N \leq 400, 10^8 \leq M \leq 10^9$ ### Phân tích và lời giải Gọi $f(i, j)$ là số cách để bật dãy bit $i$ phần tử sao cho hiện tại đang có $j$ TPLT. Ví dụ số lượng cách bật bit ở cấu hình này sẽ được đóng góp vào $f(16, 3)$. $$ ???111??11???111 $$ Ta sẽ chuyển trạng thái từ $f(i, j)$ lên. Đầu tiên khi ta đã bật $j$ TPLT, khi bật thêm một bit, ta có thể có một số lượng chọn để tạo ra thêm một số cấu hình : - **Trường hợp 1** : Bit này sẽ tạo ra một TPLT mới, ta sẽ có $j + 1$ khoảng giữa để bật bit này trực tiếp, ví dụ với cách chọn này thì ta có thể có $1??111??11???111$ từ ví dụ trên : $f(i + 1, j + 1) = f(i, j) \times (j + 1)$. - **Trường hợp 2** : Ta sẽ trực tiếp bật bit này ở đầu hoặc đuôi trong $j$ TPLT, ví dụ ta có thể có $??1111??11???111$ từ ví dụ trên : $f(i + 1, j) = f(i, j) \times 2j$ - **Trường hợp 3** : Ta sẽ bật 2 bit ở đâu hoặc đuôi trong $j$ TPLT bằng các bật một bit cách 1 đơn vị để bit ở giữa được bật, ta có $?11111??11???111$ bằng cách bật bit 2 và bit 3 sẽ được bật, ta sẽ có $2j$ cách để chọn : $f(i + 2, j) = f(i, j) \times 2j$. - **Trường hợp 4** : Ta sẽ nối hai TPLT với khoảng cách giữa hai TPLT là $2$, ta có thể nhận được $???1111111???111$ bằng cách bật bit bên trái hoặc bên phải trước giữa cầu nối, suy ra có $2 (j - 1)$ cách chọn : $f(i + 2, j - 1) = f(i, j) \times 2 (j - 1)$ - **Trường hợp 5** : Ta sẽ nối hai TPLT với khoảng cách giữa chúng là $3$, ta chỉ cần bật bit ở giữa thì hai bit kề nó sẽ được bật, ta sẽ nhận được $???111??11111111$, ta có $j - 1$ cách chọn nên suy ra : $f(i + 3, j) = f(i, j) \times (j - 1)$. Độ phức tạp tổng thể sẽ là $O(N^2)$ với việc chuyển trạng thái trong $O(1)$. ```cpp #include "bits/stdc++.h" using namespace std; const int MAX = 405; int N, mod, dp[MAX][MAX]; void add(int& a, int b){ a += b; if(a >= mod) a -= mod; } int mul(int a, int b){ return 1LL * a * b % mod; } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cin >> N >> mod; dp[0][0] = 1; for(int i = 0; i < N; ++i){ for(int j = 0; j <= i; ++j){ if(!dp[i][j]) continue; //tạo TPLT mới add(dp[i + 1][j + 1], mul(j + 1, dp[i][j])); //bật 1 bit đầu hoặc đuôi trong j TPLT hiện tại add(dp[i + 1][j], mul(2 * j, dp[i][j])); //bật 2 bit đầu hoặc đuôi trong j TPLT hiện tại add(dp[i + 2][j], mul(2 * j, dp[i][j])); if(j > 1) { //nối hai TPLT có khoảng cách là 2 add(dp[i + 2][j - 1], mul(2 * (j - 1), dp[i][j])); //nối hai TPLT có khoảng cách là 3 add(dp[i + 3][j - 1], mul(j - 1, dp[i][j])); } } } cout << dp[N][1] << '\n'; return 0; } ``` ## 3. CEOI16 Kangaroo ### Đề bài Link đề bài : https://oj.uz/problem/view/CEOI16_kangaroo **Tóm tắt đề bài :** Có khu vườn gồm $N$ và một con Kangaroo đang ở ô $cs$, nó muốn nhảy tới ô $cf \ (cs \neq cf)$ trong $N - 1$ bước, và mỗi ô đi rồi không được đi lại nữa. Một thao tác con Kangaroo di chuyển : - Giả sử nó đang ở ô $current$, ô trước đó là $prev$ và ô tiếp theo nó nhảy tới là $next$ : - Nếu $prev < current \rightarrow next < current$ - Nếu $prev > current \rightarrow next > current$ Đếm số lượng đường đi phân biệt con Kangaroo có thể thực hiện chia lấy phần dư cho $10^9 + 7$. Giới hạn : $2 \leq N \leq 2.10^3, 1 \leq cs, cf \leq N, cs \neq cf$ ### Phân tích và lời giải Đầu tiên, ta sẽ thay đổi bài toán một chút, ta sẽ đếm số cách xây dựng **hoán vị** độ dài $N$ với $p_1 = cs, p_N = cf$ hoặc $p_1 = cf, p_N = cs$ sao cho : $$ \text{Không tồn tại i} \in N, (2 \leq i \leq N - 1) \ \text{và} \ p_{i - 1} < p_i < p_{i + 1} \ \text{hoặc} \ p_{i - 1} > p_i > p_{i + 1} \ (*) $$ Ta sẽ cố định một dấu $<$ hoặc $>$ để bắt đầu xây dựng hoán vị và trong trường hợp còn lại cũng tương tự. Giả sử ta đang xây dựng các **hoán vị** từ các giá trị $1, 2, ...i$ và đã tạo được $j$ TPLT mà mỗi một trong chúng thỏa mãn $(*)$. Đầu tiên bỏ qua điều kiện hai đầu mút của bài toán một chút, ta sẽ tính số lượng hoán vị độ dài $N$ thỏa $(*)$ Giả sử ta có hai TPLT $\{1, 3, 2\}$ và $\{4, 6, 5\}$, ta muốn thêm vào đó $7$, lúc này ta không trực tiếp thêm nó vào một TPLT $\{1, 3, 2\}$ hay $\{4, 6, 5\}$, ta sẽ xét : - Gộp chúng lại thành $\{1, 3, 2, 7, 4, 6, 5\}$. Tổng quát hóa lên, nếu ta có $j$ TPLT thỏa mãn $(*)$, ta có thể dùng $i + 1$ làm cầu nối giữa hai TPLT tiếp để tạo ra $j - 1$ TPLT tất cả đều thỏa mãn $(*)$ - Tạo một TPLT mới không sinh ra đầu mút thành $\{\{1, 3, 2\}, \{7\}, \{4, 6, 5\}\}$. Trong trường hợp tổng quát ta sẽ có $j - 1$ vị trí để thêm nó vào mà một trong mỗi $j + 1$ TPLT đều thỏa $(*)$ Quay trở lại bài toán gốc. Gọi $f(i, j)$ là số cách để điền các số tự nhiên từ $1$ tới $i$ và có $j$ TPLT thỏa mãn $(*)$, phần chuyển đổi trạng thái : Ta cũng sẽ lần lượt điền các số với ý tưởng tương tự, nhưng sẽ có một chút thay đổi : - Nếu $i + 1 = cs$ hoặc $i + 1 = cf$, thì chắc chắn $i + 1$ sẽ là đầu mút của dãy, trường hợp : - Ta sẽ lấy $i + 1$ làm biên trái (hoặc phải) và thêm nó vào môt TPLT có sẵn $\rightarrow f(i + 1, j) = f(i, j)$ - Ta đặt $i + 1$ làm một TPLT mới ở biên trái (hoặc phải) $\rightarrow f(i + 1, j + 1) = f(i, j)$ - Ngược lại, ta cũng sẽ có hai trường hợp : - Ta sẽ tạo một TPLT mới chứa $i + 1$, suy ra ta sẽ có $j - 1$ cách để chọn vị trí nhưng không được lấy vị trí $cs$ hoặc $cf$ $\rightarrow f(i + 1, j + 1) = f(i, j) \times (j - 1 + [i + 1 < cs] + [i + 1 < cf])$ - Ta sẽ gộp hai TPLT với nhau, ta có $j - 1$ cách chọn vị trí đó $\rightarrow f(i + 1, j - 1) = f(i, j) \times (j - 1)$ Độ phức tạp $O(N^2)$. ```cpp #include "bits/stdc++.h" using namespace std; const int mod = 1e9 + 7; void add(int& a, int b){ a += b; if(a >= mod) a -= mod; } void sub(int& a, int b){ a -= b; if(a < 0) a += mod; } int mul(int a, int b){ return 1LL * a * b % mod; } const int MAX = 2e3 + 5; int N, S, T, dp[MAX][MAX]; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cin >> N >> S >> T; dp[0][0] = 1; for(int i = 0; i < N; ++i){ for(int j = 0; j <= i; ++j){ if(!dp[i][j]) continue; if(i + 1 == S || i + 1 == T){ //đặt vô đầu mút của TPLT trái nhất hoặc phải nhất add(dp[i + 1][j], dp[i][j]); //đưa ra làm TPLT trái nhất hoặc phải nhất add(dp[i + 1][j + 1], dp[i][j]); } else{ //tạo một tTPLT mới chứa i + 1 add(dp[i + 1][j + 1], mul(dp[i][j], j - 1 + (i + 1 < S) + (i + 1 < T))); //Ta sẽ gộp hai TPLT với nhau if(j > 1) add(dp[i + 1][j - 1], mul(dp[i][j], j - 1)); } } } cout << dp[N][1] << '\n'; return 0; } ``` ## 4. JOI Open Contest 2016 - Skyscraper ### Đề bài Link đề bài : https://oj.uz/problem/view/JOI16_skyscraper **Tóm tắt đề bài :** Cho dãy số nguyên dương $A_i$ độ dài $N$ và số nguyên dương $L$. Đếm số lượng hoán vị $p$ của $\{1, 2, ..., N\}$ thỏa mãn : $$ \sum_{i = 1}^{N - 1} |A_{p_i} - A_{p_{i + 1}}| \leq L $$ Chia lấy phần dư kết quả cho $10^9 + 7$. Giới hạn : $1 \leq N \leq 100, 1 \leq A_i \leq 10^3, 1 \leq L \leq 10^3$ ### Phân tích và lời giải Đầu tiên ta sắp xếp lại $A_i$ theo thứ tự không giảm để tiện xử lý. Ta sẽ định nghĩa thêm $A_{N + 1} = \infty$ Gọi $f(i, j, k, l)$ là số lượng cách để điền $A_1, A_2, ... A_i$ vào dãy độ dài $N$, (với những vị trí chưa được điền mang giá trị $A_{i + 1}$) và tổng giá trị của dãy hiện tại đang là $k$ và $l \ (0 \leq l \leq 2)$ đầu của hoán vị đã được điền. Vì sao lại coi những giá trị chưa được điền là $A_{i + 1}$ ? Ví dụ với $i = 3$ và $N = 6$, một cách điền ta đã sử dụng $1$ đầu mút (tức là sử dụng vị trí $1$ hoặc $N$) : $\{A_3, A_1, A_4, A_1, A_4\}$. Giờ để chuyển trạng thái từ $f(i - 1)$ lên $f(i)$, ta cần thay đổi tất cả các giá trị $A_i$ ở các vị trí trống thành $A_{i + 1}$, suy ra chi phí của việc này là $2j (A_{i + 1} - A_i)$ trừ cho các TPLT bao gồm những đầu mút của dãy tức $l(A_{i + 1} - A_i)$ Đặt $\Delta_{j,l} = (2j - l) \times (A_{i + 1} - A_i)$. Từ đây bài toán đã mất đi những phép lấy trị tuyệt đối phức tạp thông qua nhận xét này. Trạng thái hiện tại là $(i, j, k, l)$ : - **Trường hợp 1 :** Ta thêm một TPLT mới chỉ có $A_{i + 1}$ : - Không tăng thêm đầu mút sử dụng $\rightarrow f(i + 1, j + 1, k + \Delta_{j, l}, l) = f(i, j, k, l) \times (j + 1 - l)$ - Tăng số đầu mút sử dụng $\rightarrow f(i + 1, j + 1, k + \Delta_{j, l}, l + 1) = f(i, j, k, l) \times (2 - l)$ (Điều kiện là $l < 2)$ - **Trường hợp 2 :** Ta thêm $A_{i + 1}$ vào một TPLT đã có sẵn : - Không tăng thêm số đầu mút sử dụng $\rightarrow f(i + 1, j, k + \Delta_{j, l}, l) = f(i, j, k, l) \times (2j - l)$ - Tăng số đầu mút sử dụng $\rightarrow f(i + 1, j, k + \Delta_{j, l}, l + 1) = f(i, j, k, l) \times (2 - l)$ (Điều kiện là $l < 2)$ - **Trường hợp 3 :** Dùng $A_{i + 1}$ làm cầu nối giữa hai TPLT (Lúc này số đầu mút sử dụng không thay đổi) $\rightarrow f(i + 1, j - 1, k + \Delta_{j, l}, l) = f(i, j, k, l) \times (j - 1)$ Độ phức tạp $O(N^2L)$. ```cpp #include "bits/stdc++.h" using namespace std; const int mod = 1e9 + 7; const int MAX = 1e3 + 5; void add(int& a, int b){ a += b; if(a >= mod) a -= mod; } int mul(int a, int b){ return 1LL * a * b % mod; } int n, L, a[MAX], dp[101][101][1001][3]; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cin >> n >> L; for(int i = 1; i <= n; ++i){ cin >> a[i]; } if(n == 1){ //trường hợp đặt biệt cout << 1 << '\n'; return 0; } sort(a + 1, a + n + 1); dp[1][1][0][0] = 1; dp[1][1][0][1] = 2; //đặt 1 hoặc ở N for(int i = 1; i < n; ++i){ for(int j = 1; j <= i; ++j){ for(int k = 0; k <= L; ++k){ for(int l = 0; l < 3; ++l){ int& ret = dp[i][j][k][l]; if(!ret) continue; int sum = k + (2 * j - l) * (a[i + 1] - a[i]); //chi phí hiện tại if((2 * j - l) < 0 || sum > L) continue; //Ta thêm một TPLT và không tăng thêm đầu mút sử dụng add(dp[i + 1][j + 1][sum][l], mul(ret, j + 1 - l)); //Ta thêm một TPLT và tăng số đầu mút sử dụng if(l < 2) add(dp[i + 1][j + 1][sum][l + 1], mul(ret, 2 - l)); //Ta thêm a[i + 1] vào một TPLT đã có sẵn và không tăng thêm số đầu mút sử dụng add(dp[i + 1][j][sum][l], mul(ret, 2 * j - l)); //Ta thêm a[i + 1] vào một TPLT đã có sẵn và tăng thêm số đầu mút sử dụng if(l < 2) add(dp[i + 1][j][sum][l + 1], mul(ret, 2 - l)); //Dùng a[i + 1] nối giữa hai TPLT if(j > 0) add(dp[i + 1][j - 1][sum][l], mul(ret, j - 1)); } } } } int res = 0; for(int i = 0; i <= L; ++i){ add(res, dp[n][1][i][2]); } cout << res << '\n'; return 0; } ``` ## 5. Codeforces 704B : Ant Man ### Đề bài Link đề bài : https://codeforces.com/contest/704/problem/B **Tóm tắt đề bài** : Có $n$ vị trí trên hệ trục tọa độ $Ox$, vị trí thứ $i$ nằm ở tạo độ nguyên dương $x_i$ (Dữ kiện đề cho $x_1 < x_2 < x_3 < ... < x_n$) và có bốn tham số nguyên dương $a_i, b_i, c_i, d_i$. Chi phí để di chuyển từ vị trí thứ $i$ sang vị trí thứ $j$ là : - Nếu $i < j :$ $|x_i - x_j| + d_i + a_j$. - Nếu $i > j :$ $|x_i - x_j| + c_i + b_j$. Bạn muốn di chuyển qua $n$ vị trí, mỗi vị trí chỉ được đến đúng $1$ lần và bạn phải bắt đầu ở vị trí $s$ và kết thúc ở vị trí $e$. Tìm đường đi di chuyển với tổng chi phí là nhỏ nhất có thể. Giới hạn : $1 \leq N \leq 5000, 1 \leq s, e \leq n, s \neq e, 1 \leq x_1 < x_2 < x_3 < ... < x_n \leq 10^9, 1 \leq a_i, b_i, c_i, d_i \leq 10^9$. ### Phân tích và lời giải Lưu ý ta có dữ kiện $x_i < x_{i + 1}$ đề bài đã cho ta biết trước. Khi nhìn vào đề bài, chúng ta có thể cảm nhận được đây là một bài dạng **TSP (Traveling Salesman Problem)** nhưng lại có một số giới hạn, tính chất để chúng ta có thể giải được. Ở các bài toán trước, chúng ta chỉ biết mới công cụ của quy hoạch động trên TPLT và xử lý các bài toán đếm các hoán vị thỏa mãn tính chất nào đó, nhưng ở bài này, chúng ta sẽ xử lý chi phí nhỏ nhất của một hoán vị được định nghĩa dựa trên hàm $f(p)$ của đề bài yêu cầu. Hoán vị $p$ ta cần dựng có dạng $p_1 = s, ..., p_n = e$ và tổng của $\sum_{i = 1}^{n - 1} cost(p_i, p_{i + 1})$ nhỏ nhất có thể, với $cost(i, j)$ là chi phí để di chuyển từ vị trí $i$ sang vị trí $j$ theo định nghĩa của đề bài. Đặt trạng thái $f(i, j)$ là chi phí nhỏ nhất để ta dựng một hoán vị với $i$ vị trí đầu tiên và có $j$ TPLT. Ta có $4$ thao tác chuyển trạng thái khi ở trạng thái $(i, j)$ ta có thể sử dụng là : - Thêm $i + 1$ vô đầu của một trong những TPLT. - Thêm $i + 1$ vô đuôi của một trong những TPLT. - Thêm $i + 1$ vào giữa hai TPLT và nối chúng lại. - Tạo TPLT mới chỉ có $i + 1$. Ta có $3$ trường hợp cần lưu ý khi chuyển từ trạng thái $(i, j)$ lên $(i + 1, x)$ : Giờ đến với phần chuyển trạng thái cho chi phí. Ta sẽ tận dụng việc $x_i < x_{i + 1}$ để điền lần lượt các giá trị $x$ tăng dần. Đầu tiên để dễ hình dung, ta xét các giá trị $a_i, b_i, c_i, d_i$ đều bằng $0$. Giả sử ta có cấu hình sau : $$ ???125?643??? \rightleftharpoons \{ \{1, 2, 5\}, \{6, 4, 3\} \} $$ Ta cũng giả sử $1, 2, 3, 4, 5, 6, 7$ đều không chứa $s$ và $e$, giờ ta thêm $7$ để nối giữa hai TPLT $\{1, 2, 5\}$ và $\{6, 4, 3\}$, ta sẽ nhận được $\{1, 2, 5, 7, 6, 5, 3\}$. Chi phí cho trường hợp này là : $$ (x_2 - x_1) + (x_5 - x_2) + (x_7 - x_5) + (x_7 - x_6) + (x_6 - x_4) + (x_4 - x_3) \\ \\ = (x_7 - x_1) + (x_7 - x_3) = 2x_7 - x_1 - x_3 $$ Kết quả của chi phí di chuyển $\sum_{i = 1}^{n - 1} |x_{p_i}-x_{p_{i + 1}}|$ trong công thức này rất gọn, nhưng vì sao lại như vậy ? Giờ ta sẽ **hình dung** một hoán vị bất kỳ giống như một **dãy núi**. Ví dụ với $N = 8, p = \{3, 2, 4, 5, 1, 8, 6, 7 \}$ nếu vẽ ra sẽ như thế này. ![image](https://hackmd.io/_uploads/H1Q6LwnVkg.png) Do đó chi phí cho hoán vị này sẽ là : $(x_3 - x_2) + (x_5 - x_2) + (x_5 - x_1) + (x_8 - x_1) + (x_8 - x_6) + (x_7 - x_6)$ Rút gọn lại ta được : $x_3 - 2x_2 + 2x_5 - 2x_1 + 2x_8 - 2x_6 + x_7$ . Từ đây ta nhận ra thay vì phải lưu hết tất cả các điểm, ta có thể tính chi phí **gián tiếp** bằng cách chỉ cần lưu lại giá trị của những **“đỉnh”** và **“đáy”** của hoán vị được định nghĩa : - Vị trí thứ $i$ được gọi là “**đỉnh”** khi : $p_{l + 1} > p_l < ...<p_{i - 2} < p_{i - 1} < p_i > p_{i + 1} > p_{i + 2} > ... > p_r < p_{r + 1} ...$ - Vị trí thứ $i$ được gọi là **“đáy”** khi : $p_{l + 1} < p_l > ...> p_{i - 2} > p_{i - 1} > p_i < p_{i + 1} < p_{i + 2} < ... < p_r > p_{r + 1} ...$ Ta thấy rằng những vị trí **“đỉnh”** đóng góp $2x_i$ còn những vị trí **“đáy”** đóng góp $-2x_i$. Còn những **“đỉnh”** hoặc **“đáy”** nằm ở hai biên (tức là $s$ và $e$) thì chỉ đóng góp hệ số $1$ lần thay vì $2$ lần. Từ đây ta có thể xử lý $f(i , j)$ bằng cách đưa công trừ $2x_i$ một cách thích hợp và lưu ý, $f(i, j)$ bây giờ của ta không chỉ lưu chi phí di chuyển trong cùng một TPLT mà còn lưu một vài $-2x_i$ hoặc $-x_i$ của các **“đáy”.** Đến đây ta có thể đưa các tham số $a_i, b_i, c_i, d_i$ khác $0$ để xử lý bài toán cuối cùng và phần còn lại là của người đọc. Độ phức tạp $O(N^2)$. ```cpp #include <bits/stdc++.h> using namespace std; const long long inf = 1e18; const int MAX = 5e3 + 5; int N, S, E; long long x[MAX], a[MAX], b[MAX], c[MAX], d[MAX], dp[MAX][MAX]; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cin >> N >> S >> E; --S, --E; for(int i = 0; i < N; ++i) cin >> x[i]; for(int i = 0; i < N; ++i) cin >> a[i]; for(int i = 0; i < N; ++i) cin >> b[i]; for(int i = 0; i < N; ++i) cin >> c[i]; for(int i = 0; i < N; ++i) cin >> d[i]; memset(dp, 0x3f, sizeof(dp)); if(S == 0){ //Trường hợp s = 0 ta chỉ có thể tạo TPLT có đầu là s dp[1][1] = -x[0] + d[0]; } else if(E == 0){ //Trường hợp e = 0 ta chỉ có thể tạo TPLT có đuôi là e dp[1][1] = -x[0] + b[0]; } else{ //Trường hợp s ≠ 0 và e ≠ 0 ta chỉ cần tạo TPLT mới dp[1][1] = -2 * x[0] + d[0] + b[0]; } for(int i = 1; i < N; ++i){ for(int j = 1; j <= i; ++j){ if(i == S){ //Trường hợp ta thêm s //Thêm s vào bên trái TPLTtrái nhất dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + x[i] + c[i]); //Tạo TPLT trái nhất chứa s dp[i + 1][j + 1] = min(dp[i + 1][j + 1], dp[i][j] - x[i] + d[i]); } if(i == E){ //Trường hợp ta thêm e //Thêm e vào bên phải TPLT phải nhất dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + x[i] + a[i]); //Tạo TPLT phải nhất chứa e dp[i + 1][j + 1] = min(dp[i + 1][j + 1], dp[i][j] - x[i] + b[i]); } if(i != S && i != E){ //Trường hợp ta thêm giá trị khác s và e /*Trường hợp thêm được ở đầu TPLT nào đó, nếu i < s thì có thể thêm ở j TPLT, ngược lại chỉ thêm ở j - 1 TPLT khác TPLT đầu tiên*/ if(i < S || j > 1) dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + b[i] + c[i]); /*Trường hợp thêm được ở đuôi TPLT nào đó, nếu i < e thì có thể thêm ở j TPLT, ngược lại chỉ thêm ở j - 1 TPLT khác TPLT cuối cùng*/ if(i < E || j > 1) dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + d[i] + a[i]); //Nối hai TPLT bằng i + 1 if(j > 1) dp[i + 1][j - 1] = min(dp[i + 1][j - 1], dp[i][j] + 2 * x[i] + a[i] + c[i]); /*Trường hợp tạo TPLT mới, chỉ i > max(s, e) thì đã bị cố định TPLT đầu và cuối nên nếu chỉ có 1 TPLT thì không thể tạo thêm*/ if(i < max(S, E) || j > 1) dp[i + 1][j + 1] = min(dp[i + 1][j + 1], dp[i][j] + -2 * x[i] + d[i] + b[i]); } } } cout << dp[N][1] << '\n'; return 0; } ``` # Bài tập ứng dụng thêm [UTS Open '21 P7 - April Fools ](https://dmoj.ca/problem/utso21p7) [2020-2021 ICPC Southwestern European Regional Contest (SWERC 2020) F. Mentors](https://codeforces.com/gym/103081/problem/F) [AtCoder Regular Contest 117 E - Zero-Sum Ranges 2](https://atcoder.jp/contests/arc117/tasks/arc117_e) [Malaysian Computing Olympiad 2017 : R. Magical Teleporter](https://codeforces.com/group/R2SERIff4f/contest/213171/problem/R) [Malaysian Computing Olympiad 2020 : D. Reading Novels](https://codeforces.com/group/IO0c6wbyI8/contest/293254/problem/D) [TOKI Regular Open Contest #11 (Div. 1) H. Route Defense](https://tlx.toki.id/problems/troc-11/H) [LightOJ : Network](https://lightoj.com/problem/network) # Tài liệu tham khảo [Additional DP Optimizations and Techniques](https://usaco.guide/adv/dp-more?lang=cpp) by [USACO](https://usaco.guide/dashboard/) [[Tutorial] Non-trivial DP Tricks and Techniques](https://codeforces.com/blog/entry/47764) by [zscoder](https://codeforces.com/profile/zscoder) [Do you really understand Connected Components DP?](https://codeforces.com/blog/entry/109293) by [TheScrasse](https://codeforces.com/profile/TheScrasse) [[Tutorial] Dp with connected components, a simple way to understand it.](https://codeforces.com/blog/entry/92602) by [humbertoyusta](https://codeforces.com/profile/humbertoyusta) [Connected Component DP](https://youkn0wwho.academy/topic-list/connected_component_dp) by [YouKn0wWho Academy](https://youkn0wwho.academy)