Bài toán LIS nâng cao và một số ứng dụng của LIS
I. Bài toán dãy con tăng dài nhất (Longest Increasing Subsequence)
1. Mở đầu
Trong bài viết trước về chủ đề Nhập môn Quy hoạch động, tôi đã giới thiệu tới các bạn những khái niệm cơ bản về Quy hoạch động, đồng thời giới thiệu một số bài toán Quy hoạch động điển hình (xem lại tại đây), trong đó có bài toán Dãy con tăng dài nhất. Tuy nhiên, tôi mới chỉ giới thiệu tới các bạn phương pháp làm đơn giản bằng thuật toán mà tôi sẽ nhắc lại nó sơ lược dưới đây:
- Gọi là độ dài dãy con tăng dài nhất kết thúc tại phần tử .
- Tìm cách ghép vào một dãy con nào đó kết thúc tại vị trí ở phía trước nó, sao cho dãy con đó là dài nhất và .
- Từ đây suy ra công thức quy hoạch động:
Với phương pháp này, độ phức tạp lên tới và không thể giải quyết bài toán với lớn hơn được. Bài toán nâng cao hơn đặt ra ở đây là:
Cho dãy số gồm phần tử $a_1, a_2, \dots, a_n \ ($với hãy xác định dãy con tăng ngặt dài nhất của dãy số đã cho?
Input:
- Dòng đầu tiên chứa số nguyên dương .
- Dòng thứ hai chứa số nguyên dương phân tách nhau bởi dấu cách - các phần tử của dãy số.
Output:
- Dòng đầu tiên đưa ra độ dài của dãy con tìm được.
- Dòng thứ hai in ra các phần tử của dãy con tìm được. Nếu tồn tại nhiều dãy con tăng có cùng độ dài, đưa ra một dãy bất kỳ.
Sample Input:
5
1 4 2 3 2
Sample Output:
3
1 2 3
2. Phân tích ý tưởng
Với mỗi giá trị ta sử dụng mảng là chỉ số của phần tử nhỏ nhất thỏa mãn độ dài dãy con tăng dài nhất kết thúc tại đúng bằng .
Ban đầu, coi rằng mới chỉ xác định được duy nhất dãy con tăng kết thúc tại vị trí thì dĩ nhiên ta có . Vẫn sử dụng mảng để lưu độ dài dãy con tăng dài nhất kết thúc tại và mảng để lưu vị trí của phần tử liền trước trong dãy con tăng dài nhất kết thúc tại .
Ta sẽ xây dựng một sơ đồ tính toán sao cho với mỗi vị trí phải biết được những điều sau:
- : Độ dài của dãy con tăng dài nhất trong đoạn . Mỗi khi xuất hiện một phần tử mới khiến cho độ dài dãy con tăng tại đó kéo dài ra thì cập nhật tăng thêm đơn vị .
- : Vị trí của phần tử nhỏ nhất thỏa mãn độ dài dãy con tăng dài nhất kết thúc tại là . Các giá trị được tính đồng thời với các trong quá trình duyệt, nên < < < \ .
Sơ đồ đó như sau:
end_pos[1] = 1;
res = 1;
for (i = 1; i <= n; i = i + 1)
{
{Tính dp[i]};
{k = dp[i]};
// Độ dài dãy con tăng dài nhất kết thúc tại a[i]
// dài hơn kết quả trước đó.
if (k > res)
{
res = k;
end_pos[res] = i;
}
// Nếu có nhiều dãy con tăng độ dài k thì ghi nhận
// phần tử kết thúc có giá trị nhỏ nhất.
else if (a[i] > a[end_pos[k]])
end_pos[k] = i;
}
Bây giờ, nếu như các bạn muốn có được dãy con tăng dài nhất độ dài kết thúc tại thì bắt buộc . Ngoài ra, nếu đem ghép vào cuối dãy con tăng dài nhất kết thúc tại mà vẫn thu được dãy tăng thì kể cả đem ghép vào cuối dãy con tăng dài nhất kết thúc tại cũng vẫn thu được dãy tăng do điều . Vì thế, để tính được ta có thể áp dụng tìm kiếm nhị phân để tìm ra độ dài lớn nhất thỏa mãn khi đó ghép vào cuối dãy con tăng dài nhất kết thúc tại .
Điều này đồng nghĩa với việc . Và dĩ nhiên ta có vì bây giờ đã là phần tử liền trước của trong dãy con tăng dài nhất kết thúc tại .
Ý tưởng như vậy là hoàn thiện, giờ chúng ta sẽ cài đặt giải thuật này!
3. Cài đặt
Ngôn ngữ C++:
#include <bits/stdc++.h>
#define task "LIQ."
#define int long long
using namespace std;
const int maxn = 1e6 + 10;
void enter(int &n, vector < int > &a)
{
cin >> n;
a.resize(n + 1, 0);
for (int i = 1; i <= n; ++i)
cin >> a[i];
}
// In kết quả và truy vết dãy con tăng dài nhất.
void print_result(int n, vector < int > &a, vector < int > &dp, vector < int > &trace)
{
int best = 1;
for (int i = 2; i <= n; ++i)
if (dp[i] > dp[best])
best = i;
cout << dp[best] << endl;
vector < int > elements;
while (best)
{
elements.push_back(a[best]);
best = trace[best];
}
for (int i = elements.size() - 1; i >= 0; --i)
cout << elements[i] << ' ';
}
/**
* Tìm kiếm nhị phân giá trị p lớn nhất mà a[end_pos[p]] < a[i].
* max_length: Độ dài dãy con tăng dài nhất đã ghi nhận được
trong đoạn a[1...i - 1].
* a: Dãy số ban đầu.
* val: Tham số đại diện cho a[i].
*/
int binary_searching(int max_length, vector < int > &a, vector < int > &end_pos, int val)
{
int p = 0;
int l = 1, r = max_length;
while (l <= r)
{
int mid = (l + r) >> 1;
if (a[end_pos[mid]] < val)
{
p = mid;
l = mid + 1;
}
else
r = mid - 1;
}
return p;
}
void solution(int n, vector < int > &a)
{
vector < int > dp(n + 1, 0);
vector < int > end_pos(n + 1, 0);
vector < int > trace(n + 1, 0);
int res = 1;
end_pos[1] = 1;
for (int i = 1; i <= n; ++i)
{
// Tìm kiếm nhị phân độ dài p tốt nhất để ghép a[i] vào phía sau
// dãy con tăng dài nhất kết thúc tại a[end_pos[p]].
int p = binary_searching(res, a, end_pos, a[i]);
int k = p + 1;
// Cập nhật độ dài dãy con tăng dài nhất hiện tại.
// Luôn giữ cho phần tử kết thúc của các dãy con tăng là nhỏ nhất có thể.
if (k > res)
{
res = k;
end_pos[k] = i;
}
else if (a[end_pos[k]] > a[i])
end_pos[k] = i;
// Cập nhật các kết quả ở vị trí i.
dp[i] = k;
trace[i] = end_pos[p];
}
print_result(n, a, dp, trace);
}
main()
{
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n;
vector < int > a;
enter(n, a);
solution(n, a);
return 0;
}
Ngôn ngữ Python:
# In kết quả và truy vết dãy con tăng dài nhất.
def print_result():
best = 1
for i in range(2, n + 1):
if dp[i] > dp[best]:
best = i
print(dp[best])
elements = []
while best != 0:
elements.append(a[best])
best = trace[best]
elements.reverse()
print(elements)
'''
* Tìm kiếm nhị phân giá trị p lớn nhất mà a[end_pos[p]] < a[i].
* max_length: Độ dài dãy con tăng dài nhất đã ghi nhận được
trong đoạn a[1...i - 1].
* a: Dãy số ban đầu.
* val: Tham số đại diện cho a[i].
'''
def binary_searching(max_length, a, end_pos, val):
p = 0
l = 1, r = max_length
while l <= r:
mid = (l + r) >> 1
if a[end_pos[mid]] < val:
p = mid
l = mid + 1
else:
r = mid - 1
return p
def solution(n, a):
dp = [0] * (n + 1)
end_pos = [0] * (n + 1)
trace = [0] * (n + 1)
res = 1
end_pos[1] = 1
for i in range(1, n + 1):
# Tìm kiếm nhị phân độ dài p tốt nhất để ghép a[i] vào phía sau
# dãy con tăng dài nhất kết thúc tại a[end_pos[p]].
p = binary_searching(res, a, end_pos, a[i])
k = p + 1
# Cập nhật độ dài dãy con tăng dài nhất hiện tại.
# Luôn giữ cho phần tử kết thúc của các dãy con tăng là nhỏ nhất có thể.
if k > res:
res = k
end_pos[k] = i
elif a[end_pos[k]] > a[i]:
end_pos[k] = i
# Cập nhật các kết quả ở vị trí i.
dp[i] = k
trace[i] = end_pos[p]
print_result(n, a, dp, trace)
if __name__ == '__main__':
n = int(input())
a = [0] * (n + 1)
for i in range(1, n + 1):
a[i] = int(input())
solution(n, a)
Đánh giá độ phức tạp: Giải thuật có độ phức tạp . Ngoài phương pháp Tìm kiếm nhị phân, bài toán này cũng có thể giải bằng cách sử dụng cấu trúc dữ liệu Interval Tree hoặc Binary Indexed Tree với độ phức tạp tương đương, nhưng tôi sẽ không đề cập ở đây vì cách đó thuộc vào phạm trù kiến thức khó hơn.
II. Một số bài toán ứng dụng
1. Tô màu dãy số
Đề bài
Cho dãy số gồm phần tử . Hãy tìm cách tô màu các phần tử của dãy số bằng ít màu nhất có thể, sao cho các phần tử được tô cùng màu thì đều tạo thành dãy con không tăng?
Input:
- Dòng đầu tiên chứa số nguyên dương - số lượng phần tử của dãy số .
- Dòng thứ hai chứa số nguyên phân tách nhau bởi dấu cách.
Output:
- Số nguyên duy nhất là số lượng màu tối thiểu cần sử dụng để tô màu dãy số.
Sample Input:
6
5 2 4 1 3 0
Sample Output:
2
Phân tích ý tưởng
Có thể khẳng định rằng, số lượng màu ít nhất cần sử dụng chính là độ dài của dãy con tăng dài nhất trong dãy .
Chứng minh: Gọi là độ dài dãy con tăng dài nhất, và là số lượng tối thiểu dãy con không tăng sao cho những dãy đó chứa toàn bộ các phần tử của dãy số. Ta sẽ chứng minh rằng .
Thật vậy, ta thấy rằng trường hợp là không thể xảy ra, bởi vì một khi ta đã có phần tử tăng ngặt, thì không thể có hai phần tử nào trong tập đó cùng thuộc vào một dãy con không tăng. Do đó, mỗi phần tử trong dãy con tăng dài nhất phải thuộc vào một dãy con không tăng khác nhau, nhờ thế .
Bây giờ, giả sử . Coi như ta đã có một tập gồm dãy con không tăng, mỗi dãy tô một màu và là nhỏ nhất (tối ưu). Ta biến đổi tập các dãy này theo cách sau:
- Chọn ra hai dãy con sao cho dãy thứ nhất bắt đầu trước dãy thứ hai trong dãy số ban đầu, và phần tử bắt đầu của dãy thứ nhất lớn hơn hoặc bằng phần tử bắt đầu của dãy thứ hai.
- Kế đến, lấy phần tử bắt đầu của dãy thứ nhất đem ghép vào dãy thứ hai (đổi màu tô cho nó).
- Thực hiện như vậy sau một số bước hữu hạn, chắc chắn ta sẽ thu được dãy con mà các phần tử bắt đầu của chúng tạo thành một dãy con tăng độ dài . Mà là độ dài dãy con tăng dài nhất, nên mâu thuẫn với giả sử.
Vì thế, chắc chắn và ta có điều phải chứng minh.
Cài đặt
Do bài toán không yêu cầu truy vết lại dãy con tăng dài nhất, nên ta có thể cải tiến cài đặt bằng cách sử dụng hàm tìm kiếm nhị phân có sẵn trong C++ hoặc Python. Ý tưởng là lưu dãy vào một mảng - tức là lưu phần tử nhỏ nhất mà dãy con tăng dài nhất kết thúc tại nó có độ dài rồi tìm kiếm nhị phân trên mảng để chọn ra độ dài nhỏ nhất mà khi đó ta sẽ xem xét thay thành phần tử cuối của dãy con tăng độ dài . Còn nếu không tìm thấy giá trị nào như vậy, nghĩa là dãy con tăng kết thúc tại được nối dài thành .
Ngôn ngữ C++:
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 10;
void enter(int &n, vector < int > &a)
{
cin >> n;
a.resize(n + 1, 0);
for (int i = 1; i <= n; ++i)
cin >> a[i];
}
void solution(int n, vector < int > &a)
{
vector < int > d(n + 1, 0);
int res = 0;
for (int i = 1; i <= n; ++i)
{
int p = lower_bound(d.begin() + 1, d.begin() + res + 1, a[i]) - d.begin();
res = max(res, p);
d[p] = a[i];
}
cout << res;
}
main()
{
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n;
vector < int > a;
enter(n, a);
solution(n, a);
return 0;
}
Ngôn ngữ Python:
def solution(n, a):
d = [0] * (n + 1)
res = 1
d[1] = a[0]
for i in range(1, n):
p = res + 1
l, r = 1, res
while l <= r:
mid = (l + r) // 2
if d[mid] >= a[i]:
p = mid
r = mid - 1
else:
l = mid + 1
res = max(res, p)
d[p] = a[i]
print(res)
if __name__ == '__main__':
n = int(input())
a = [int(i) for i in input().split()]
solution(n, a)
2. Dãy con hình nón
Đề bài
Cho một dãy số gồm phần tử . Một dãy con của được gọi là dãy con hình nón nếu như trong dãy đó tồn tại một vị trí thỏa mãn:
Hãy tìm dãy con hình nón dài nhất trong dãy đã cho?
Input:
- Dòng đầu tiên chứa số nguyên dương - số phần tử dãy số .
- Dòng thứ hai chứa số nguyên phân tách nhau bởi dấu cách.
Output:
- Số nguyên duy nhất là độ dài dãy con hình nón dài nhất tìm được.
Sample Input:
6
1 5 2 8 9 5 0
Sample Output:
5
Phân tích ý tưởng
Ta nhận thấy, một dãy con hình nón sẽ được chia làm hai nửa: nửa phía trước là một dãy con tăng ngặt, nửa phía sau là một dãy con giảm ngặt, và hai dãy này sẽ có chung phần tử ở giữa.
Gọi là độ dài dãy con tăng dài nhất kết thúc tại xét theo chiều từ tới . Tương tự, gọi là độ dài dãy con tăng dài nhất kết thúc tại nhưng xét theo chiều từ về . Ta tính hai mảng này bằng phương pháp Quy hoạch động kết hợp với Tìm kiếm nhị phân giống như bài toán dãy con tăng dài nhất.
Sau đó, xét mọi vị trí ta sẽ có được độ dài dãy con hình nón nhận làm tâm là: . Chọn kết quả lớn nhất ở tất cả các vị trí ta sẽ thu được kết quả cuối cùng.
Cài đặt
Ngôn ngữ C++:
#include <bits/stdc++.h>
#define int long long
#define task "wavio."
using namespace std;
void enter(int &n, vector < int > &a)
{
cin >> n;
a.resize(n + 1, 0);
for (int i = 1; i <= n; ++i)
cin >> a[i];
}
void solution(int &n, vector < int > &a)
{
vector < int > d(n + 1, 0);
vector < int > l(n + 1, 0);
vector < int > r(n + 1, 0);
int max_length = 0;
for (int i = 1; i <= n; ++i)
{
int p = lower_bound(d.begin() + 1, d.begin() + max_length + 1, a[i]) - d.begin();
max_length = max(max_length, p);
l[i] = p;
d[p] = a[i];
}
d.resize(n + 1, 0);
max_length = 0;
for (int i = n; i >= 1; --i)
{
int p = lower_bound(d.begin() + 1, d.begin() + max_length + 1, a[i]) - d.begin();
max_length = max(max_length, p);
r[i] = p;
d[p] = a[i];
}
int res = 0;
for (int i = 1; i <= n; ++i)
res = max(res, r[i] + l[i] - 1);
cout << res;
}
main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n;
vector < int > a;
enter(n, a);
solution(n, a);
return 0;
}
Ngôn ngữ Python:
def solution(n, a):
d = [0] * (n + 1)
l = [0] * (n + 1)
r = [0] * (n + 1)
max_length = 1
d[1] = a[0]
for i in range(1, n):
p = max_length + 1
l, r = 1, res
while l <= r:
mid = (l + r) // 2
if d[mid] >= a[i]:
p = mid
r = mid - 1
else:
l = mid + 1
max_length = max(max_length, p)
d[p] = a[i]
max_length = 1
d[1] = a[-1]
for i in range(n - 2, -1, -1):
p = max_length + 1
l, r = 1, res
while l <= r:
mid = (l + r) // 2
if d[mid] >= a[i]:
p = mid
r = mid - 1
else:
l = mid + 1
max_length = max(max_length, p)
d[p] = a[i]
res = 0
for i in range(0, n):
res = max(res, l[i] + r[i] - 1)
print(res)
if __name__ == '__main__':
n = int(input())
a = [int(i) for i in input().split()]
solution(n, a)
III. Tài liệu tham khảo
- https://cp-algorithms.com/sequences/longest_increasing_subsequence.html
- Competitive Programming 3 - Steven Halim & Felix Halim.
- Sách Giải thuật và Lập trình - thầy Lê Minh Hoàng.
- Tài liệu giáo khoa chuyên Tin quyển 1 - thầy Hồ Sĩ Đàm.
©️ Tác giả: Vũ Quế Lâm từ Viblo
All Rights Reserved