Tóm tắt đề bài

Cho \(N\) viên gạch, mỗi viên có kích thước chiều dài \(a_i\), chiều rộng \(b_i\) và chiều cao \(h_i\). Một viên gạch \(j\) có thể đặt lên trên viên gạch \(i\) nếu và chỉ nếu \(a_j < a_i\) và \(b_j < b_i\). Các viên gạch được xếp thành một tháp thẳng đứng.
Yêu cầu:

1. Tìm số lượng viên gạch tối đa có thể xếp chồng lên nhau.
2. Tìm chiều cao lớn nhất có thể đạt được của tháp gạch.

Phân tích

• Điều kiện xếp chồng: Viên \(j\) nằm trên viên \(i\) khi \(a_j < a_i\) và \(b_j < b_i\). Đây là một quan hệ thứ tự bán phần.
• Giới hạn: \(N \le 5000\). Với giới hạn này, ta có thể sử dụng thuật toán có độ phức tạp \(O(N^2)\).
• Tính chất: Bài toán này là một biến thể của bài toán "Dãy con tăng dài nhất" (Longest Increasing Subsequence - LIS) nhưng trên không gian hai chiều (chiều dài và chiều rộng) và có trọng số (chiều cao).
• Quan sát: Để dễ dàng kiểm tra điều kiện xếp chồng, ta nên sắp xếp các viên gạch theo một chiều (ví dụ chiều dài \(a_i\) tăng dần). Khi đó, viên gạch thứ \(i\) chỉ có thể đặt lên trên các viên gạch đứng trước nó trong danh sách đã sắp xếp nếu thỏa mãn đồng thời cả hai điều kiện về \(a\) và \(b\).

Hướng giải quyết

1. Tiền xử lý

• Lưu trữ thông tin mỗi viên gạch dưới dạng một cấu trúc hoặc pair.
• Sắp xếp danh sách các viên gạch theo chiều dài \(a_i\) tăng dần. Nếu \(a_i\) bằng nhau, có thể sắp xếp theo \(b_i\).

2. Quy hoạch động

Gọi:

• \(t[i]\) là số viên gạch tối đa của một tháp kết thúc tại viên gạch thứ \(i\) (viên \(i\) nằm trên cùng).
• \(d[i]\) là chiều cao tối đa của một tháp kết thúc tại viên gạch thứ \(i\).

Công thức truy hồi:
Với mỗi viên gạch \(i\) (từ \(1\) đến \(N\)), ta duyệt qua tất cả các viên gạch \(j\) đứng trước nó (\(1 \le j < i\)):

• Nếu \(a_j < a_i\) và \(b_j < b_i\):
  • \(t[i] = \max(t[i], t[j] + 1)\)
  • \(d[i] = \max(d[i], d[j] + h_i)\)
• Lưu ý: Giá trị khởi tạo của \(t[i]\) là \(1\) và \(d[i]\) là \(h_i\) (bản thân viên gạch \(i\) tạo thành một tháp).

Kết quả cuối cùng là giá trị lớn nhất trong mảng \(t\) và mảng \(d\).

3. Lưu ý về cách xoay

Theo đề bài: "Các cạnh của các viên gạch song song với nhau". Điều này ngụ ý chúng ta không được tự ý xoay viên gạch (đổi \(a_i\) cho \(b_i\)) trừ khi đề bài cho phép. Trong mã nguồn tham khảo, các viên gạch được giữ nguyên kích thước \(a, b\) như dữ liệu nhập vào.

Độ phức tạp

• Thời gian: \(O(N^2)\) do có hai vòng lặp lồng nhau để thực hiện quy hoạch động.
• Bộ nhớ: \(O(N)\) để lưu trữ mảng quy hoạch động và danh sách các viên gạch.

Code tham khảo

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

// Sử dụng pair để lưu (chiều dài, chiều rộng) và chiều cao
typedef pair<pair<long long, long long>, long long> Brick;

long long n;
long long t[5005]; // t[i]: số viên gạch tối đa của tháp kết thúc tại i
long long d[5005]; // d[i]: chiều cao tối đa của tháp kết thúc tại i
Brick a[5005];

int main() {
    // Tối ưu tốc độ nhập xuất
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    if (!(cin >> n)) return 0;

    for (int i = 1; i <= n; i++) {
        cin >> a[i].first.first >> a[i].first.second >> a[i].second;
    }

    // Sắp xếp gạch theo chiều dài tăng dần để dễ truy hồi
    sort(a + 1, a + 1 + n);

    long long max_bricks = 0;
    long long max_height = 0;

    for (int i = 1; i <= n; i++) {
        // Khởi tạo: tháp chỉ có mình viên gạch i
        t[i] = 1;
        d[i] = a[i].second;

        for (int j = 1; j < i; j++) {
            // Kiểm tra điều kiện viên j có thể nằm dưới viên i không
            // (Trong code này a[j] là viên nhỏ hơn, a[i] là viên lớn hơn)
            // Lưu ý: Để xếp i lên trên j thì a[j] > a[i] và b[j] > b[i]
            // Ở đây ta đang tính toán theo hướng: i là viên trên cùng, j là viên dưới nó
            if (a[j].first.first < a[i].first.first && a[j].first.second < a[i].first.second) {
                t[i] = max(t[i], t[j] + 1);
                d[i] = max(d[i], d[j] + a[i].second);
            }
        }
        // Cập nhật kết quả tối ưu toàn cục
        max_bricks = max(max_bricks, t[i]);
        max_height = max(max_height, d[i]);
    }

    cout << max_bricks << " " << max_height << endl;

    return 0;
}