Hướng dẫn giải của Dãy Con Tăng 4
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Tác giả: ceaturs
Sử dụng Định lý Dilworth (phiên bản áp dụng cho chuỗi số):
Với một dãy gồm ~N~ số, số lượng nhỏ nhất các dãy con tăng nghiêm ngặt (không giao nhau) mà bạn cần để bao phủ toàn bộ dãy ban đầu = độ dài của dãy con giảm dài nhất (LDS).
-Nói đơn giản là: Min số dãy con tăng nghiêm ngặt để cover toàn bộ dãy = Longest Decreasing Subsequence (LDS).
🔸 Ví dụ:
Trong đề cho dãy:
5
3 1 2 5 4
Ta có dãy con giảm dài nhất: 3 1(là các số đầu tiên của các dãy con tăng nếu chia ra), độ dài là 2.
→ Ít nhất cần 2 dãy con tăng để bao phủ toàn bộ dãy.
📌 Lưu ý:
- Các dãy con không cần liên tiếp, chỉ cần giữ thứ tự.
- Mỗi phần tử chỉ thuộc 1 dãy con.
- Đây là ứng dụng của Dilworth's Theorem trong bài toán sắp xếp hoặc phân tách chuỗi.
Bình luận