Hiểu bài toán

Bài toán "Tặng Quà" yêu cầu tìm cách chọn các gói quà để tổng trọng lượng không vượt quá một giới hạn cho trước W, tối đa hóa tổng giá trị. Tuy nhiên, dựa trên các giải pháp được cung cấp (sử dụng cây phân đoạn hoặc BIT để tìm dãy con tăng dài nhất có trọng số tăng), bài toán thực chất là một biến thể của bài toán tìm dãy con tăng dài nhất (LIS) trên 2 chiều (trọng số và giá trị). Cụ thể, với mỗi gói quà có tọa độ (a[i], w[i]), ta cần tìm đường đi dài nhất trên lưới sao cho tọa độ cả hai chiều đều tăng dần. Các giải pháp sử dụng BIT (Fenwick Tree) hoặc Segment Tree để tối ưu hóa việc tìm max value cho các phần tử có tọa độ nhỏ hơn.

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

Cách Quy hoạch động với BIT (Fenwick Tree)

#include <bits/stdc++.h>
#define ll long long
#define m 500005
using namespace std;

vector<ll> F(m, 0);

void update(int i, ll x) {
    while (i < m) {
        F[i] = max(F[i], x);
        i += i & -i;
    }
}

ll query(int i) {
    ll kq = 0;
    while (i > 0) {
        kq = max(kq, F[i]);
        i -= i & -i;
    }
    return kq;
}

ll solve(vector<int>& a, vector<int>& w) {
    int n = a.size();
    vector<ll> dp(n);

    // Co dinh hoa chi so
    vector<int> c = a;
    sort(c.begin(), c.end());
    c.erase(unique(c.begin(), c.end()), c.end());

    for(int i = 0; i < n; i++) {
        a[i] = lower_bound(c.begin(), c.end(), a[i]) - c.begin() + 1;
    }

    // Sap xep theo chieu w giam dan, neu bang thi theo a giam dan
    vector<int> p(n);
    iota(p.begin(), p.end(), 0);
    sort(p.begin(), p.end(), [&](int i, int j) {
        if (w[i] != w[j]) return w[i] < w[j];
        return a[i] < a[j];
    });

    ll res = 0;
    for(int idx : p) {
        ll val = query(a[idx] - 1) + 1;
        res = max(res, val);
        update(a[idx], val);
    }
    return res;
}

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

Giải pháp này sử dụng Quy hoạch động kết hợp với BIT để tối ưu hóa.

1. Chuẩn hóa dữ liệu: Do tọa độ a[i] có thể lớn, ta cần giảm miền giá trị (coordinate compression) để có thể dùng BIT.
2. Sắp xếp: Các gói quà được sắp xếp theo thứ tự tăng dần của trọng lượng w. Điều này đảm bảo khi xử lý một gói quà, tất cả các gói quà có trọng lượng nhỏ hơn (và có thể là ứng viên cho dãy con trước đó) đã được xử lý.
3. Quy hoạch động: Với mỗi gói quà idx, dp[idx] là độ dài dãy con tăng dài nhất kết thúc tại gói quà đó. dp[idx] = 1 + max(dp[j]) với mọi j sao cho a[j] < a[idx] và w[j] < w[idx].
4. Cây BIT: BIT được dùng để lưu trữ giá trị dp lớn nhất cho các chỉ số a. Khi xử lý gói quà idx, ta truy vấn BIT tại chỉ số a[idx] - 1 để tìm giá trị lớn nhất của các phần tử có chỉ số a nhỏ hơn. Sau đó ta cập nhật BIT tại chỉ số a[idx] bằng giá trị dp[idx] vừa tính được.
5. Kết quả: Giá trị lớn nhất tìm được trong suốt quá trình chính là độ dài dãy con tăng dài nhất.

Cách Tối ưu hóa với Segment Tree

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int MAXN = 1000005;
int tree[MAXN * 4];

void update(int node, int start, int end, int idx, int val) {
    if (start == end) {
        tree[node] = max(tree[node], val);
        return;
    }
    int mid = (start + end) / 2;
    if (idx <= mid) update(node * 2, start, mid, idx, val);
    else update(node * 2 + 1, mid + 1, end, idx, val);
    tree[node] = max(tree[node * 2], tree[node * 2 + 1]);
}

int query(int node, int start, int end, int l, int r) {
    if (r < start || end < l) return 0;
    if (l <= start && end <= r) return tree[node];
    int mid = (start + end) / 2;
    return max(query(node * 2, start, mid, l, r), query(node * 2 + 1, mid + 1, end, l, r));
}

int main() {
    // Input handling and logic similar to BIT approach
    // ...
    return 0;
}

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

Segment Tree cũng giải quyết bài toán theo hướng quy hoạch động tương tự BIT. Cấu trúc cây phân đoạn cho phép truy vấn max trên một khoảng [1, a[i] - 1] và cập nhật tại vị trí a[i].

Cách hoạt động:

1. Chuẩn hóa dữ liệu và sắp xếp theo w tăng dần (giống BIT).
2. Duyệt qua các gói quà, với mỗi gói (a, w):
   • Truy vấn max value trên khoảng [1, a - 1] để lấy kết quả dãy con trước đó.
   • Cập nhật vị trí a bằng giá trị mới (giá trị cũ + 1).

So với BIT, Segment Tree linh hoạt hơn nhưng thường có hệ số thường lớn hơn và code phức tạp hơn một chút cho bài toán max prefix/suffix.

Cách Brute Force (Quy hoạch động cơ bản)

// Pseudocode for Brute Force
int n;
struct Gift { int a, w; } gifts[1005];
int dp[1005];

int solve() {
    sort(gifts, gifts + n, [](Gift x, Gift y) {
        if (x.w != y.w) return x.w < y.w;
        return x.a < y.a;
    });

    int ans = 0;
    for (int i = 0; i < n; i++) {
        dp[i] = 1;
        for (int j = 0; j < i; j++) {
            if (gifts[j].a < gifts[i].a && gifts[j].w < gifts[i].w) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        ans = max(ans, dp[i]);
    }
    return ans;
}

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

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

1. Sắp xếp các gói quà theo trọng lượng w tăng dần.
2. Dùng mảng dp, dp[i] là độ dài dãy con tăng dài nhất kết thúc tại gói quà thứ i.
3. Với mỗi i, duyệt qua tất cả j < i để kiểm tra điều kiện a[j] < a[i]. Nếu thỏa mãn, cập nhật dp[i] = max(dp[i], dp[j] + 1).

Cách này chỉ hiệu quả với dữ liệu nhỏ (N <= 1000) vì độ phức tạp O(N^2).

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

Bài học kinh nghiệm

• Bài toán là tìm dãy con tăng (LIS) 2 chiều: (a, w).
• Giải pháp tối ưu cần kết hợp sắp xếp (theo 1 chiều) và cấu trúc dữ liệu cây (BIT/Segment Tree) để tối ưu chiều còn lại.
• Coordinate Compression là kỹ thuật bắt buộc nếu giá trị đầu vào lớn.

Lỗi thường gặp

• Xử lý sai thứ tự ưu tiên khi sort (phải sort theo w tăng dần, nếu w bằng thì a tăng dần).
• Lỗi chỉ số trong BIT/Segment Tree (thường là lỗi off-by-one).
• Quên dùng long long cho các biến giá trị.