Hướng giải của DP co ban voi Li Chao

Nhớ rằng hướng dẫn giải này chỉ nên sử dụng khi bế tắc, và tuyệt đối không nên sao chép mã nguồn kèm theo. Hãy tôn trọng tác giả bài tập và người viết hướng dẫn giải.
Nộp mã nguồn lời giải chính thức trước khi giải bài tập đó có thể khiến bạn bị ban.

Tác giả: kienadmin

Huong dan giai

Sử dụng cây Li Chao (Li Chao Segment Tree) để tối ưu DP.

Bai toan quy hoach dong co cong thuc: \[dp_i = c_i + \min_{j < i} (dp_j + a_j \times b_i)\]

Dat:

  • He so goc: \(m_j = a_j\)
  • Tung do goc: \(c_j' = dp_j\)
  • Hoanh do truy van: \(x_i = b_i\)

Ta can tim duong thang co gia tri nho nhat tai \(x_i\). Day chinh la bai toan CHT (Convex Hull Trick) co the giai bang Li Chao Tree vi cac he so goc khong co tinh don dieu.

Thuat toan
  1. Khoi tao Li Chao Tree voi tap cac gia tri \(b_i\) (nen toa do).
  2. \(dp_1 = c_1\), them duong thang \((a_1, dp_1)\) vao cay.
  3. Voi \(i\) tu \(2\) den \(N\):
    • \(dp_i = c_i + \text{query}(b_i)\)
    • Them duong thang \((a_i, dp_i)\) vao cay.
  4. In ra \(dp_N\).

Chu y: Khong co \(j\) nao truoc \(i = 1\), nen \(dp_1 = c_1\).

Do phuc tap

\(O(N \log N)\).

Ma nguon C++

// Giải thuật lc cho bài toán lc-dp-basic\n#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 4e18;

struct Line {
    ll m, c;
    ll eval(ll x) const { return m * x + c; }
};

struct LiChao {
    vector<ll> xs;
    vector<Line> tree;
    int n;

    LiChao(vector<ll> qx) : xs(qx) {
    sort(xs.begin(), xs.end());
    // Sap xep mang
        xs.erase(unique(xs.begin(), xs.end()), xs.end());
        n = xs.size();
        tree.assign(4 * n, {0, INF});
    }

    void add(Line nw, int node, int l, int r) {
        int m = (l + r) / 2;
        Line &cur = tree[node];
        bool mb = nw.eval(xs[m]) < cur.eval(xs[m]);
        if (mb) swap(cur, nw);
        if (l == r) return;
        bool lb = nw.eval(xs[l]) < cur.eval(xs[l]);
        if (lb != mb) add(nw, node * 2, l, m);
        else add(nw, node * 2 + 1, m + 1, r);
    }

    void add(ll m, ll c) { add({m, c}, 1, 0, n - 1); }

    ll query(int idx, int node, int l, int r) {
        ll res = tree[node].eval(xs[idx]);
        if (l == r) return res;
        int m = (l + r) / 2;
        if (idx <= m) return min(res, query(idx, node * 2, l, m));
        else return min(res, query(idx, node * 2 + 1, m + 1, r));
    }

    ll query(ll x) {
        int idx = lower_bound(xs.begin(), xs.end(), x) - xs.begin();
        return query(idx, 1, 0, n - 1);
    }
};

int main() {
    // Doc du lieu dau vao
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int N; cin >> N;
    vector<ll> a(N + 1), b(N + 1), c(N + 1);
    vector<ll> qx;
    for (int i = 1; i <= N; i++) {
        cin >> a[i] >> b[i] >> c[i];
        qx.push_back(b[i]);
    }
    LiChao lichao(qx);
    ll dp = c[1];
    lichao.add(a[1], dp);
    for (int i = 2; i <= N; i++) {
        dp = c[i] + lichao.query(b[i]);
        lichao.add(a[i], dp);
    }
    cout << dp << "\n";
    return 0;
}

Chu y: \(dp_1 = c_1\) vi khong co \(j\) nao truoc do. Voi \(i \ge 2\), ta su dung Li Chao Tree da co cac duong thang tu nhung vong truoc.

Nhận xét

Không có ý kiến tại thời điểm này.