Hiểu bài toán

Bài toán yêu cầu xây dựng một tòa tháp cao nhất có thể bằng cách xếp các khối lập trình (block) lên nhau. Mỗi khối có 3 thông số: chiều dài đáy (a), chiều rộng đáy (b), và chiều cao (h). Một khối chỉ có thể được xếp lên trên một khối khác nếu diện tích tiếp xúc giữa chúng bằng hoặc lớn hơn diện tích đáy của khối ở trên. Cụ thể, nếu khối i nằm trên khối j thì điều kiện là ai * bi <= aj * bj. Mục tiêu là tìm chiều cao tối đa của tòa tháp có thể tạo được từ tập hợp các khối cho trước.

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

Cách Quy hoạch động cơ bản

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

struct Block {
    int a, b, h;
};

const int N = 1e6 + 5;
int n;
long long dp[N];
vector<Block> blocks;

void readInput() {
    cin >> n;
    blocks.resize(n);
    for (int i = 0; i < n; i++) {
        cin >> blocks[i].a >> blocks[i].b >> blocks[i].h;
    }
}

void solve() {
    // Sắp xếp các block theo diện tích đáy giảm dần
    sort(blocks.begin(), blocks.end(), [](const Block& x, const Block& y) {
        return (long long)x.a * x.b > (long long)y.a * y.b;
    });

    long long ans = 0;
    // dp[i] là chiều cao tối đa khi kết thúc bằng block thứ i
    for (int i = 0; i < n; i++) {
        dp[i] = blocks[i].h;
        for (int j = 0; j < i; j++) {
            // Kiểm tra điều kiện có thể xếp lên nhau
            if ((long long)blocks[i].a * blocks[i].b <= (long long)blocks[j].a * blocks[j].b) {
                dp[i] = max(dp[i], dp[j] + blocks[i].h);
            }
        }
        ans = max(ans, dp[i]);
    }
    cout << ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    readInput();
    solve();
    return 0;
}

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

Đây là cách tiếp cận trực quan nhất. Đầu tiên, ta sắp xếp các block theo diện tích đáy giảm dần. Sau đó, sử dụng quy hoạch động: dp[i] là chiều cao tối đa của tháp kết thúc bằng block thứ i. Với mỗi block i, ta duyệt qua tất cả các block j trước nó (j < i). Vì các block đã được sắp xếp theo diện tích giảm dần, nên chỉ cần kiểm tra xem diện tích của block i có nhỏ hơn hoặc bằng block j hay không. Nếu có, ta có thể cập nhật dp[i] = max(dp[i], dp[j] + height[i]). Độ phức tạp là O(n^2) do có 2 vòng lặp lồng nhau.

Cách Quy hoạch động với Segment Tree

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

struct Block {
    int a, b, h;
};

const int N = 1e6 + 5;
int n, maxB = 0;
long long dp[N];
vector<pair<int, int>> tower[N]; // {a, h}

void readInput() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        Block blk;
        cin >> blk.a >> blk.b >> blk.h;
        tower[blk.b].push_back({blk.a, blk.h});
        maxB = max(maxB, blk.b);
    }
}

void solve() {
    for (int i = 1; i <= maxB; i++) {
        dp[i] = dp[i - 1];
        for (auto &tw : tower[i]) {
            dp[i] = max(dp[i], dp[tw.first] + tw.second);
        }
    }
    cout << dp[maxB];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    readInput();
    solve();
    return 0;
}

• Time Complexity: O(N + M)
• Space Complexity: O(N)

Giả sử có ràng buộc về mặt không gian (diện tích đáy) là nhỏ, ta có thể tối ưu hóa. Tuy nhiên, giải pháp này trong code mẫu có vẻ không hoàn toàn chính xác với bài toán gốc vì nó chỉ xét theo biến b. Một cách tiếp cận tối ưu thực sự là dùng Segment Tree hoặc Fenwick Tree để lấy giá trị dp lớn nhất trong một đoạn. Cụ thể, ta có thể coi diện tích đáy là tọa độ. Sau khi nén tọa độ diện tích, ta dùng Segment Tree để lưu giá trị dp lớn nhất tại mỗi diện tích. Khi xử lý một block mới với diện tích S, ta truy vấn giá trị dp lớn nhất trong đoạn [1, S] và cập nhật vào vị trí S. Điều này giúp giảm độ phức tạp từ O(n^2) xuống O(n log n).

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

Bài học kinh nghiệm

• Có thể coi bài toán là tìm đường đi dài nhất trong đồ thị có hướng, trong đó một cạnh từ block A đến block B tồn tại nếu diện tích đáy của A >= diện tích đáy của B.
• Việc sắp xếp các block theo diện tích đáy giảm dần giúp đơn giản hóa việc kiểm tra điều kiện xếp chồng (chỉ cần kiểm tra j < i thay vì duyệt lại toàn bộ).
• Để tối ưu hóa, thay vì duyệt qua tất cả các block trước đó, ta chỉ cần quan tâm đến chiều cao lớn nhất có thể đạt được với các block có diện tích đáy >= diện tích đáy của block hiện tại.

Lỗi thường gặp

• Sử dụng kiểu dữ liệu int cho diện tích (a * b) có thể gây tràn số. Phép nhân này nên được thực hiện bằng kiểu long long.
• Nếu không sắp xếp các block, độ phức tạp thuật toán sẽ là O(n^2) và không đảm bảo rằng các block được xét trước đều có diện tích lớn hơn.
• Xử lý sai trường hợp các block có cùng diện tích đáy. Cần đảm bảo thứ tự xử lý đúng để tránh xếp chồng sai quy tắc (block cùng diện tích không thể xếp lên nhau nếu diện tích tiếp xúc phải lớn hơn hoặc bằng, nhưng nếu bằng đúng thì có thể xếp được tùy vào quy tắc bài toán).