Hiểu bài toán

Bài toán yêu cầu chọn một số sách tối đa sao cho có thể xếp chồng lên nhau. Mỗi sách có 2 thông số: độ dày (d) và chiều rộng (r). Điều kiện để xếp chồng sách A lên sách B là: độ dày của A phải nhỏ hơn hoặc bằng độ dày của B (dA ≤ dB) và chiều rộng của A phải nhỏ hơn hoặc bằng chiều rộng của B (rA ≤ rB). Bài toán tìm số lượng sách lớn nhất có thể xếp chồng theo thứ tự thỏa mãn điều kiện.

Đây là bài toán tìm Chuỗi con tăng dài nhất (Longest Increasing Subsequence - LIS) trên 2 chiều, nhưng có thể biến đổi về LIS 1 chiều bằng cách sắp xếp.

Các cách tiếp cận

Cách Quy hoạch động O(N^2)

#include <bits/stdc++.h>
using namespace std;

struct Book {
    int d, r;
};

bool cmp(const Book &a, const Book &b) {
    if (a.d == b.d) return a.r > b.r;
    return a.d < b.d;
}

int main() {
    ifstream fin("ChonSach.Inp");
    ofstream fout("ChonSach.Out");
    int n;
    fin >> n;
    vector<Book> books(n);
    for (int i = 0; i < n; ++i) fin >> books[i].d >> books[i].r;

    sort(books.begin(), books.end(), cmp);

    vector<int> dp(n, 1);
    int ans = 1;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < i; ++j) {
            // Chỉ xét chuyển tiếp nếu sách j có thể xếp lên sách i (đảm bảo thứ tự sau khi sort)
            if (books[j].r <= books[i].r) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        ans = max(ans, dp[i]);
    }
    fout << ans << endl;
    return 0;
}

• Time Complexity: O(N^2)
• Space Complexity: O(N)

Cách tiếp cận này sử dụng quy hoạch động kinh điển cho bài toán LIS. Sau khi sắp xếp tăng dần theo độ dày (và giảm dần theo chiều rộng nếu bằng), ta chỉ cần tìm LIS trên chiều rộng. Với mỗi sách i, ta duyệt qua tất cả các sách j < i và cập nhật dp[i] = max(dp[i], dp[j] + 1) nếu sách j có thể xếp lên i (điều kiện là books[j].r <= books[i].r). Độ phức tạp là O(N^2) do có 2 vòng lặp lồng nhau.

Cách Tối ưu bằng Binary Search O(N log N)

#include <bits/stdc++.h>
using namespace std;

struct Book {
    int d, r;
};

bool cmp(const Book &a, const Book &b) {
    if (a.d == b.d) return a.r > b.r;
    return a.d < b.d;
}

int main() {
    ifstream fin("ChonSach.Inp");
    ofstream fout("ChonSach.Out");
    int n;
    fin >> n;
    vector<Book> books(n);
    for (int i = 0; i < n; ++i) fin >> books[i].d >> books[i].r;

    sort(books.begin(), books.end(), cmp);

    vector<int> tail; // Mảng lưu giá trị cuối cùng của dãy con tăng dài nhất có độ dài k
    for (auto &b : books) {
        int r = b.r;
        // Tìm vị trí để chèn r vào mảng tail
        auto it = lower_bound(tail.begin(), tail.end(), r);
        if (it == tail.end()) {
            tail.push_back(r);
        } else {
            *it = r;
        }
    }
    fout << tail.size() << endl;
    return 0;
}

• Time Complexity: O(N log N)
• Space Complexity: O(N)

Đây là cách tối ưu để tìm LIS. Sau khi sắp xếp, ta duyệt qua từng sách và duy trì một mảng 'tail' (hoặc 'dp') trong đó tail[i] là giá trị cuối cùng nhỏ nhất có thể của dãy con tăng dài nhất có độ dài i + 1. Với mỗi chiều rộng r của sách hiện tại, ta dùng hàm lower_bound để tìm vị trí thích hợp trong mảng tail để chèn r vào. Nếu r lớn hơn tất cả các phần tử trong tail, ta mở rộng dãy con. Nếu không, ta thay thế phần tử đầu tiên trong tail có giá trị >= r bằng r. Việc này đảm bảo tail luôn tăng dần và tìm được độ dài LIS.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Vấn đề 2 chiều có thể biến đổi về 1 chiều bằng cách sắp xếp tăng dần theo chiều này và tìm LIS trên chiều còn lại.
• Để đảm bảo không chọn nhầm sách có cùng độ dày nhưng chiều rộng không phù hợp, khi sắp xếp, nếu độ dày bằng nhau ta cần sắp xếp giảm dần theo chiều rộng.
• Bài toán tìm dãy con tăng dài nhất (LIS) có thể giải quyết hiệu quả với độ phức tạp O(N log N) bằng kỹ thuật dùng mảng tail và binary search.

Lỗi thường gặp

• Sai lệch trong việc sắp xếp: Nếu chỉ sắp xếp tăng dần theo cả 2 chiều, ta có thể lặp sai thứ tự. Ví dụ (d=1, r=2) và (d=1, r=1). Nếu sắp xếp tăng dần cả 2, (d=1, r=1) sẽ đứng trước. Nếu ta chỉ so sánh điều kiện d tăng dần và r tăng dần, ta có thể không chọn được chuỗi tối ưu. Đúng là sắp xếp d tăng, r giảm.
• Quên sử dụng biến lưu giá trị cuối cùng của dãy con tăng dài nhất (mảng tail) trong cách tiếp cận O(N log N) và thay vào đó dùng mảng dp thông thường.
• Không chú ý đến kiểu dữ liệu (int/long long) nếu dữ liệu đầu vào lớn.