Hướng giải của Mua dat - DP mua dat dong
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ả:
Huong dan giai
Day la bai toan USACO "ACQUIRE" kinh dien.
Buoc 1: Tien xu ly
Sap xep cac thua dat theo \(w\) tang dan. Neu \(w\) bang nhau, giu lai thua dat co \(l\) lon nhat. Sau do, cac thua dat con lai se co \(w\) tang dan va \(l\) giam dan. Thua dat nao bi "dominate" (ca \(w\) va \(l\) deu nho hon thua dat khac) co the loai bo.
Buoc 2: Quy hoach dong
Sau khi loai bo, \(w\) tang, \(l\) giam. DP: \[dp_i = \min_{j < i} \{ dp_j + w_i \times l_{j+1} \}\]
Dat:
- He so goc: \(m_j = l_{j+1}\)
- Tung do goc: \(c_j = dp_j\)
- Hoanh do: \(w_i\)
Can tim \(\min (m_j \cdot w_i + c_j)\).
Vi \(l_{j+1}\) giam dan, ta co the dung Static CHT Deque. Nhung de the hien tinh dong cua Li Chao, ta them cac duong thang theo thu bat ky (khong can sap xep).
Do phuc tap
\(O(N \log N)\).
Ma nguon C++
// Giải thuật lc cho bài toán lc-dp-land\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<pair<ll, ll>> a(N);
for (int i = 0; i < N; i++) cin >> a[i].first >> a[i].second;
sort(a.begin(), a.end());
// Sap xep mang
vector<pair<ll, ll>> b;
for (auto &p : a) {
while (b.size() && b.back().second <= p.second) b.pop_back();
b.push_back(p);
}
int M = b.size();
vector<ll> w(M + 1), l(M + 1);
for (int i = 0; i < M; i++) {
w[i + 1] = b[i].first;
l[i + 1] = b[i].second;
}
vector<ll> qx;
for (int i = 1; i <= M; i++) qx.push_back(w[i]);
LiChao lichao(qx);
lichao.add(l[1], 0);
ll dp = 0;
for (int i = 1; i <= M; i++) {
dp = lichao.query(w[i]);
if (i < M) lichao.add(l[i + 1], dp);
}
cout << dp << "\n";
return 0;
}
Giai thich: \(dp_i = \min_{j < i} (dp_j + w_i \times l_{j+1})\). Them duong thang cho moi \(j\): he so goc \(m = l_{j+1}\), tung do goc \(c = dp_j\).
Nhận xét