Hướng giải của Hang rao - DP CHT 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
Sử dụng cây Li Chao (Li Chao Segment Tree) để tối ưu DP.
Goi \(dp_i\) la chi phi nho nhat de son den cot \(i\) va cot \(i\) la cot tru:
\[dp_i = K + \min_{j < i} \{ dp_j + (x_i - x_j) \times h_j \}\]
Khai trien: \[dp_i = K + x_i \cdot \min_{j < i} \{ -h_j \} + \min_{j < i} \{ dp_j - x_j \cdot h_j + x_i \cdot h_j \}\]
That ra: \[dp_i = K + \min_{j < i} \{ dp_j + x_i \cdot h_j - x_j \cdot h_j \}\] \[dp_i = K + \min_{j < i} \{ (dp_j - x_j \cdot h_j) + h_j \cdot x_i \}\]
Dat:
- He so goc: \(m_j = h_j\)
- Tung do goc: \(c_j = dp_j - x_j \cdot h_j\)
- Hoanh do truy van: \(x_i\)
Ta can tim \(\min (m_j \cdot x_i + c_j)\), day la bai toan CHT.
Vi cac \(h_j\) khong don dieu, ta dung Li Chao Tree. Them duong thang ban dau: \(m = h_1, c = -x_1 \cdot h_1\) (vi \(dp_1 = K\)).
Khong can sap xep vi Li Chao Tree cho phep them bat ky.
Do phuc tap
\(O(N \log N)\).
Ma nguon C++
// Giải thuật lc cho bài toán lc-dp-fence\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; ll K; cin >> N >> K;
vector<ll> x(N + 1), h(N + 1);
vector<ll> qx;
for (int i = 1; i <= N; i++) {
cin >> x[i] >> h[i];
qx.push_back(x[i]);
}
LiChao lichao(qx);
lichao.add(h[1], K - x[1] * h[1]);
ll dp = K;
for (int i = 2; i <= N; i++) {
dp = K + lichao.query(x[i]);
lichao.add(h[i], dp - x[i] * h[i]);
}
cout << dp << "\n";
return 0;
}
Nhận xét