Hiểu bài toán

Bài toán yêu cầu xây dựng một tháp cao nhất có thể bằng cách sử dụng các khối Rubik (hoặc các khối xây dựng) có giới hạn. Với mỗi loại khối i, ta có:

• Chiều cao mỗi khối: h_i
• Số lượng: c_i
• Giới hạn độ cao tối đa: a_i (không khối nào được vượt quá độ cao này)

Điều này có nghĩa là khi xếp các khối lên nhau, tổng chiều cao tại mọi điểm không được vượt quá a_i của khối đó. Ta cần tìm tổng chiều cao lớn nhất có thể đạt được.

Giới hạn: K ≤ 400, hi ≤ 100, ci ≤ 10, a_i ≤ 40000.

Ví dụ mẫu: Với 3 loại khối, ta cần chọn số lượng từng loại sao cho tổng chiều cao tối đa nhưng vẫn thỏa mãn ràng buộc a_i.

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

Cách Quy hoạch động cơ bản với xử lý đa trọng

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

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

int main() {
    int K;
    cin >> K;
    vector<Block> blocks(K);
    for (int i = 0; i < K; ++i) {
        cin >> blocks[i].h >> blocks[i].a >> blocks[i].c;
    }

    // Sắp xếp theo giới hạn a tăng dần
    sort(blocks.begin(), blocks.end(), [](const Block& x, const Block& y) {
        return x.a < y.a;
    });

    const int MAXA = 40000;
    vector<int> dp(MAXA + 1, -1);
    dp[0] = 0;

    for (const auto& block : blocks) {
        int h = block.h;
        int a = block.a;
        int c = block.c;

        // Dùng deque optimization cho mỗi residue class
        for (int mod = 0; mod < h; ++mod) {
            deque<pair<int, int>> dq; // {value, position}
            for (int j = mod; j <= a; j += h) {
                if (dp[j] != -1) {
                    int val = dp[j] - j / h;
                    while (!dq.empty() && dq.back().first <= val) {
                        dq.pop_back();
                    }
                    dq.push_back({val, j});
                }
                while (!dq.empty() && (j - dq.front().second) / h > c) {
                    dq.pop_front();
                }
                if (!dq.empty()) {
                    dp[j] = max(dp[j], dq.front().first + j / h);
                }
            }
        }
    }

    int ans = 0;
    for (int i = 0; i <= MAXA; ++i) {
        if (dp[i] != -1) ans = max(ans, i);
    }
    cout << ans << endl;
    return 0;
}

• Time Complexity: O(K * MAXA * log(c)) hoặc O(K * MAXA) với deque optimization
• Space Complexity: O(MAXA)

Phương pháp này sử dụng quy hoạch động kết hợp với kỹ thuật deque optimization để xử lý ràng buộc số lượng.

1. Sắp xếp các khối theo giới hạn a tăng dần: Điều này đảm bảo khi xét đến một khối có giới hạn a, tất cả các khối trước đó đều có giới hạn >= a, giúp việc thỏa mãn ràng buộc dễ dàng hơn.

2. Quy hoạch động: dp[i] = số lượng khối còn lại có thể dùng khi đạt chiều cao i. Nếu dp[i] = -1 thì không thể đạt chiều cao i.

3. Deque optimization: Để xử lý ràng buộc số lượng ci, ta chia các độ cao thành các nhóm theo residue modulo hi. Với mỗi nhóm, ta dùng deque để tìm max của dp[j] - j/hi trong khoảng window ci.

4. Cập nhật: dp[j] = max(dp[j], max{k} (dp[j - k*h] + k)) với k ≤ ci

Cách này tối ưu hóa từ O(K * MAXA * c) xuống O(K * MAXA).

Cách Quy hoạch động với đổi bài toán sang túi đồ giới hạn

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

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

int main() {
    int K;
    cin >> K;
    vector<Block> blocks(K);
    for (int i = 0; i < K; ++i) {
        cin >> blocks[i].h >> blocks[i].a >> blocks[i].c;
    }

    sort(blocks.begin(), blocks.end(), [](const Block& x, const Block& y) {
        return x.a < y.a;
    });

    vector<int> dp(40001, -1);
    dp[0] = 0;

    for (const auto& block : blocks) {
        int h = block.h;
        int a = block.a;
        int c = block.c;

        // Duyệt từ 0 đến a
        for (int j = 0; j <= a; ++j) {
            if (dp[j] >= 0) {
                // Có thể đạt độ cao j, reset số lượng
                dp[j] = c;
            } else if (j >= h && dp[j - h] > 0) {
                // Thêm một khối nếu còn số lượng
                dp[j] = dp[j - h] - 1;
            }
        }
    }

    int ans = 0;
    for (int j = 0; j <= 40000; ++j) {
        if (dp[j] >= 0) ans = j;
    }
    cout << ans << endl;
    return 0;
}

• Time Complexity: O(K * MAXA)
• Space Complexity: O(MAXA)

Đây là cách tiếp cận đơn giản hơn, biến đổi bài toán:

1. Ý tưởng: dp[j] = số lượng khối còn lại của loại hiện tại khi đạt chiều cao j.

2. Logic cập nhật:

   • Nếu dp[j] >= 0: nghĩa là có thể đạt j bằng cách dùng các khối trước, giờ có thể dùng thêm c_i khối mới
   • Nếu dp[j] < 0 nhưng dp[j - h] > 0: có thể thêm một khối mới vào

3. Sắp xếp theo a: Đảm bảo khi xét đến độ cao j, tất cả các khối trước đều có giới hạn >= j.

4. Kết quả: độ cao j lớn nhất sao cho dp[j] != -1.

Cách này dựa trên ý tưởng 'không cần quan tâm đến số lượng cụ thể, chỉ cần biết có thể tiếp tục xây hay không'.

Cách Quy hoạch động cơ bản (không tối ưu)

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

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

int main() {
    int K;
    cin >> K;
    vector<Block> blocks(K);
    for (int i = 0; i < K; ++i) {
        cin >> blocks[i].h >> blocks[i].a >> blocks[i].c;
    }

    // Sắp xếp theo giới hạn a
    sort(blocks.begin(), blocks.end(), [](const Block& x, const Block& y) {
        return x.a < y.a;
    });

    const int MAXA = 40000;
    vector<bool> dp(MAXA + 1, false);
    dp[0] = true;

    int ans = 0;
    for (const auto& block : blocks) {
        int h = block.h;
        int a = block.a;
        int c = block.c;

        // Dùng multiple knapsack
        for (int k = 1; k <= c; ++k) {
            for (int j = a; j >= h; --j) {
                if (dp[j - h]) {
                    dp[j] = true;
                }
            }
        }

        // Cập nhật ans chỉ với các độ cao <= a
        for (int j = 0; j <= a; ++j) {
            if (dp[j]) ans = max(ans, j);
        }
    }

    cout << ans << endl;
    return 0;
}

• Time Complexity: O(K * c * MAXA)
• Space Complexity: O(MAXA)

Đây là cách tiếp cận trực tiếp nhất:

1. dp[j] = true nếu có thể đạt chiều cao j

2. Với mỗi loại khối, dùng multiple knapsack để thử tất cả số lượng từ 1 đến c_i

3. Vòng lặp ngược (j từ a về h) để đảm bảo mỗi khối chỉ được dùng 1 lần trong mỗi lần cập nhật

4. Sau khi xử lý mỗi loại, cập nhật kết quả với các độ cao <= giới hạn a của loại đó

Cách này dễ hiểu nhưng chậm do không tối ưu hóa số lần lặp.

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

Bài học kinh nghiệm

• Phải sắp xếp các khối theo giới hạn a tăng dần. Điều này đảm bảo khi xét đến một độ cao j, tất cả các khối đã xét đều có giới hạn >= j, nên ta chỉ cần quan tâm đến số lượng.
• Bài toán có thể biến đổi thành bài toán túi đồ với ràng buộc số lượng, và có thể tối ưu bằng deque optimization hoặc phương pháp đổi giá trị.
• Với c_i ≤ 10 và K ≤ 400, các phương pháp O(K * MAXA) đều có thể chấp nhận được (400 * 40000 = 16 triệu).

Lỗi thường gặp

• Quên sắp xếp theo a: Nếu không sắp xếp, ta có thể dùng một khối có giới hạn nhỏ ở độ cao lớn hơn giới hạn của nó.
• Xử lý sai ràng buộc số lượng: Phải đảm bảo số lượng khối dùng không vượt quá c_i.
• Lựa chọn sai hướng lặp: Trong multiple knapsack phải lặp ngược để tránh dùng nhiều lần.
• Quên kiểm tra điều kiện ai khi cập nhật kết quả: Chỉ các độ cao <= ai của khối hiện tại và các khối trước mới hợp lệ.