Hướng dẫn giải của Xây đập giữ vàng

Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Lời giải này đang bị ẩn cho đến khi bạn chọn mở ra.

Chúng tôi khuyên bạn nên tự thử giải bài trước. Việc mở lời giải có thể làm lộ mất ý tưởng chính trước khi bạn có cơ hội tự giải.

Bạn phải đăng nhập để mở lời giải này.

Đăng nhập

Tác giả: Hiếu Nguyễn, haidang3004, zuanopro, 111_LeQuangTam

Hiểu bài toán

Đề bài yêu cầu tìm một đoạn mỏ vàng liên tiếp từ chỉ số L đến R sao cho tổng trữ lượng vàng của các mỏ trong đoạn đó là lớn nhất, với điều kiện đoạn kè xây dựng được từ đá của các mỏ trong đoạn đó phải đủ dài để che chắn cho tất cả các mỏ. Giả sử mỏ L nằm ở tọa độ $xL$ và mỏ R nằm ở $xR$. Chiều dài đoạn kè cần thiết để che chắn từ $xL$ đến $xR$ là $xR - xL$. Tổng độ dài đá có sẵn từ các mỏ L đến R là $\sum{i=L}^R ri$. Điều kiện để đoạn kè tồn tại là $\sum{i=L}^R ri \ge xR - xL$. Ta cần tìm $\max \sum{i=L}^R gi$ thỏa mãn điều kiện trên.

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

Cách Quy hoạch động với BIT (Tối ưu)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = (1LL<<60);

struct BITMin {
    int n; vector<ll> f;
    BITMin(int n=0): n(n), f(n+1, INF) {}
    void update(int i, ll v){ for(; i<=n; i+=i&-i) f[i] = min(f[i], v); }
    ll query(int i){ ll r=INF; for(; i>0; i-=i&-i) r = min(r, f[i]); return r; }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n; 
    if(!(cin >> n)) return 0;
    vector<ll> x(n+1), g(n+1), r(n+1);
    for(int i=1;i<=n;i++) cin >> x[i] >> g[i] >> r[i];

    vector<ll> PR(n+1,0), PG(n+1,0);
    for(int i=1;i<=n;i++){ PR[i]=PR[i-1]+r[i]; PG[i]=PG[i-1]+g[i]; }

    vector<ll> A(n+1), B(n+1), coord; coord.reserve(2*n);
    for(int i=1;i<=n;i++){
        A[i] = PR[i-1] - x[i];
        B[i] = PR[i]   - x[i];
        coord.push_back(A[i]);
        coord.push_back(B[i]);
    }
    sort(coord.begin(), coord.end());
    coord.erase(unique(coord.begin(), coord.end()), coord.end());
    auto getRank = [&](ll val) {
        return lower_bound(coord.begin(), coord.end(), val) - coord.begin() + 1;
    };
    int m = coord.size();
    BITMin bit(m);

    ll ans = 0;
    for(int i=1;i<=n;i++){
        int rB = getRank(B[i]);
        ll minVal = bit.query(rB);
        if(minVal != INF) ans = max(ans, PG[i] - minVal);
        int rA = getRank(A[i]);
        bit.update(rA, PG[i-1]);
    }
    cout << ans << endl;
}
  • Time Complexity: O(n log n)
  • Space Complexity: O(n)

Đây là phương pháp tối ưu nhất. Ta quy hoạch động để tìm đoạn kết thúc tại mỏ R. Để điều kiện $\sum{i=L}^R ri \ge xR - xL$ thỏa mãn, ta biến đổi: $PR[R] - PR[L-1] \ge xR - xL \iff PR[L-1] - xL \ge PR[R] - xR$. Gọi $Ai = PR[i-1] - xi$ và $Bi = PR[i] - xi$. Với mỗi mỏ R, ta cần tìm mỏ L ($L \le R$) sao cho $AL \ge BR$ và $PG[L-1]$ là nhỏ nhất để $PG[R] - PG[L-1]$ là lớn nhất. Sử dụng cây BIT (Fenwick Tree) hoặc Segment Tree để lưu trữ các giá trị $PG[L-1]$ theo tọa độ của $AL$. Ta duyệt R từ 1 đến n, tại mỗi R, ta truy vấn BIT để tìm giá trị nhỏ nhất trong vùng $AL \ge BR$, sau đó cập nhật BIT với giá trị $PG[R]$ tại tọa độ $AR$. Do các giá trị $Ai, Bi$ có thể rất lớn, ta cần chuẩn hóa (coordinate compression).

Cách Brute Force
// Pseudocode
long long max_gold = 0;
for (int L = 1; L <= n; ++L) {
    long long current_r = 0;
    long long current_g = 0;
    for (int R = L; R <= n; ++R) {
        current_r += r[R];
        current_g += g[R];
        if (current_r >= x[R] - x[L]) {
            max_gold = max(max_gold, current_g);
        }
    }
}
cout << max_gold;
  • Time Complexity: O(n^2)
  • Space Complexity: O(n)

Sử dụng hai vòng lặp lồng nhau để thử tất cả các đoạn liên tiếp [L, R]. Với mỗi đoạn, tính tổng r và tổng g, kiểm tra điều kiện $\sum r \ge x[R] - x[L]$. Nếu thỏa mãn, cập nhật kết quả tối đa.

Cách Quy hoạch động cơ bản (Duyệt L và R)
// Pseudocode
// DP[i] là tổng vàng lớn nhất có thể bảo vệ khi mỏ i là mỏ cuối cùng
// Cần thêm mảng để lưu tổng r để kiểm tra điều kiện
long long DP[n+1];
DP[0] = 0;
long long ans = 0;
for (int i = 1; i <= n; ++i) {
    DP[i] = g[i]; // Khởi tạo với đoạn chỉ bao gồm mỏ i
    long long current_r = r[i];
    // Thử kéo dài đoạn về trước
    for (int j = i-1; j >= 1; --j) {
        current_r += r[j];
        if (current_r >= x[i] - x[j]) {
            DP[i] = max(DP[i], DP[j] + g[i]); // Cập nhật nếu nối được
        } else {
            // Có thể break sớm nếu điều kiện không thỏa mãn và r >= 0
        }
    }
    ans = max(ans, DP[i]);
}
  • Time Complexity: O(n^2)
  • Space Complexity: O(n)

Phương pháp quy hoạch động này vẫn cần duyệt tất cả các cặp L, R có thể để tìm cách nối đoạn tối ưu. Trong trường hợp xấu nhất (tất cả r đều dương), độ phức tạp vẫn là O(n^2).

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

Cách tiếp cận Time Space Tên
1 O(n log n) O(n) Quy hoạch động với BIT (Tối ưu)
2 O(n^2) O(n) Brute Force
3 O(n^2) O(n) Quy hoạch động cơ bản (Duyệt L và R)

Bài học kinh nghiệm

  • Bài toán có thể coi là bài toán tìm đoạn con thỏa mãn điều kiện bất đẳng thức trên tổng tiền tố.
  • Việc biến đổi điều kiện $PR[R] - PR[L-1] \ge xR - xL$ thành $PR[L-1] - xL \ge PR[R] - xR$ cho phép tách các biến L và R, tạo điều kiện sử dụng cấu trúc dữ liệu để tối ưu.

Lỗi thường gặp

  • Lỗi integer overflow khi tính tổng (nên dùng long long).
  • Xử lý sai trường hợp đoạn chỉ bao gồm 1 mỏ (L=R).

Bình luận

Please read the guidelines before commenting.

Không có bình luận tại thời điểm này.