Editorial for Atcoder Educational DP Contest Z - Frog 3
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Phân tích:
Gọi ~dp[i]~ là chi phí nhỏ nhất để đi từ hòn đá ~1~ đến hòn đá ~i~. Với độ phức tạp ~O(N^2)~ ta có:
Khai triển biểu thức trên ta có:
Với ~dp[j] -2h_i h_j + h_j^2~ ta có thể viết lại thành ~(-2h_j)x + (dp[j] + h_j^2)~ với ~x = h_i~, đây là phương trình có dạng ~(mx + b)~. Đến đây, ta cần truy vấn giá trị tối thiểu với ~x = h_i~ bằng cách sử dụng Convex Hull Trick.
Độ phức tạp: ~O(N)~.
Code:
#include <bits/stdc++.h> using namespace std; using ll = long long; struct Line { ll k, m, p; bool operator<(const Line& o) const { return k < o.k; } bool operator<(ll x) const { return p < x; } ll eval(ll x) const { return k * x + m; } }; deque<Line> hull; int n; ll c, inf = LLONG_MAX; vector<ll> h, dp; ll division(ll a, ll b) { // floored division return a / b - ((a < 0) != (b < 0) && a % b); } bool isect(Line &x, const Line &y) { if (x.k == y.k) x.p = x.m > y.m ? inf : -inf; else x.p = division(y.m - x.m, x.k - y.k); return x.p >= y.p; } void add(ll k, ll m) { Line L = {k, m, 0}; while ((int) hull.size() >= 2 && (isect(L, hull.back()), isect(hull.back(), hull[(int) hull.size() - 2]), L.p < hull.back().p)) hull.pop_back(); hull.push_back(L); } ll query(ll x) { while ((int) hull.size() >= 2 && hull[0].eval(x) >= hull[1].eval(x)) hull.pop_front(); return hull[0].eval(x); } void ins(int i, vector<ll> &h, vector<ll> &dp) { add(-h[i] * 2, (dp[i] + (h[i] * h[i]))); } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n >> c; vector<ll> h(n), dp(n); for (ll&x : h) cin >> x; dp[0] = 0; ins(0, h, dp); for (int i = 1; i < n; ++i) { ll x = query(h[i]); dp[i] = c + (h[i] * h[i]) + x; ins(i, h, dp); } cout << dp[n - 1] << '\n'; }
Comments