Chuẩn hóa dữ liệu:

Để việc cài đặt sau này trở nên đơn giản dễ hiểu hơn, ta sẽ chuẩn hóa dữ liệu bằng cách cho ~b[i]=K-b[i]+1~. Lúc này bài toán đưa thành tìm dãy con dài nhất sao ~a[i] \leq a[i+1]~ và ~b[i] \leq b[i+1]~.

Subtask 1: ~N \leq 20, M,K \leq 20~

Ta có N tương đối nhỏ, nên ta có thể quay lui tất cả các cạnh chọn

Time complexity: ~O(2^N*N)~

Subtask 2: ~N \leq 1000, M,K \leq 1000~

Ở subtask này, ta có thể nhìn ra công thức quy hoạch động đơn giản là ~dp[i]=max(dp[i],dp[j]+1)~ với ~j~ thỏa mãn ~j<i, a[j] \leq a[i], b[j] \leq b[i]~</p>

Time complexity: ~O(N^2)~

Subtask 3: ~N \leq 100000, M \leq 1000, K=1~

Với ~K=1~, việc chọn dãy con sẽ không còn phụ thuộc vào giá trị ~b[i]~ nữa. Lúc này bài toán trở thành tìm dãy con không giảm dài nhất đơn thuần

Time complexity: ~N*{log_2}(N)~

Subtask 4: ~N \leq 100000~, ~M,K \leq 20~

Từ subtask này trở đi, ta sẽ tiếp cận bài toán theo một hướng khác một chút với subtask 2. Gọi ~dp[x][y]~ là độ dài dãy con dài nhất thỏa đề và có phần tử cuối cùng có cao độ bằng ~x~ và trường độ bằng ~y~. Lúc này, với mỗi phần tử ~i~, ta chỉ cần duyệt toàn bộ và chọn giá trị ~dp[x][y]~ lớn nhất thỏa mãn ~x \leq a[i]~ và ~y \leq b[i]~. Lúc này, độ dài dãy con thỏa đề có phần tử cuối cùng ở vị trí ~i~ sẽ là giá trị này thêm ~1~. Sau đó, ta chỉ cần cập nhật lại ~dp[a[i]][b[i]]~ nữa là được.

Time complexity: ~O(N*M*K)~

Subtask 5: ~N \leq 100000, M,K \leq 1000~

Ở subtask này, ta có thể thực hiện công việc tìm giá trị lớn nhất của subtask 4 nhanh hơn bằng cách sử dụng 1 CTDL bất kỳ.

Time complexity: ~O(N*{log_2}(M)*{log_2}(K))~

Một cách tiếp cận khác:

Đây là cách làm ban đầu mình nghĩ tới khi mới bắt đầu viết đề, nhưng sau đó nhận ra là có thể giải đơn giản hơn bằng cách mình vừa chia sẻ ở trên. Các bạn có thể tham khảo thêm cách làm sau đây:

Gọi ~f[i][j]~ là giá trị ~b~ nhỏ nhất là kết thúc của dãy con thỏa đề độ dài ~j~ khi xét tất cả các phần tử có giá trị ~a~ không lớn hơn ~i~. Ta nhận thấy với mỗi ~i~ thì ~f[i][j]~ sẽ không giảm (chứng minh tương tự như dãy con tăng không giảm dài nhất thông thường). Vì thế, ta có thể áp dụng chặt nhị phân. Với mỗi phần tử ở vị trí ~i~, ta sẽ tìm ~p~ là vị trí bé nhất thỏa ~f[a[i]][p]>b[i]~ bằng chặt nhị phân, khi đó độ dài dãy con thỏa đề với vị trí kết thúc là ~i~ sẽ là ~p~. Sau đó, ta có thể cập nhật mảng ~f~ bằng cách gán ~f[j][p]=min(f[j][p],b[i])~ với ~a[i] \leq j \leq M~.

Time complexity: ~O(N*({log_2}(N)+M))~

As long as it works