DPまとめコンテスト Z - Frog 3
問題
$ N個の足場$ 1,2,\dots,Nがありそれぞれ高さ$ h_iです。$ h_iは単調増加します。
足場$ iから足場$ jへの遷移コストは$ (h_j - h_i)^2 + Cです。
足場$ 1から$ Nへ遷移する場合の最小コストはいくつでしょう?
制約
$ 2 \leq N \leq 2 \times 10^5
$ 1 \leq C \leq 10^{12}
$ 1\leq h_1 < h_2 < \dots < h_N \leq 10^6
考察
$ {\rm dp}_{i}を$ 0から$ iまで移動する最小コストとすると、
$ {\rm dp}_i = \min_{j=0}^{i-1} \{ {\rm dp}_j + (h_i - h_j)^2 + C \}
$ = \min_{j=0}^{i-1} \{ {\rm dp}_j + h_j^2 - 2 h_i h_j \} + h_i^2 + C
です($ jに依らないものは外に出した)。
ここで$ f_j(x) = {\rm dp}_j + h_j^2 - 2 h_j xとすると、
$ {\rm dp}_i = \min_{j=0}^{i-1} \{ f_j(h_i) \} + h_i^2 + C
で、この計算は$ i本の直線群の$ h_iにおける最小値を求めることに相当することがわかります。
code:cpp
using namespace std;
typedef long long ll;
#define rep(i, N) for (int i = 0; i < (int)N; ++i) #define all(a) (a).begin(), (a).end() template <typename T>
class LiChaoTree {
class Line {
public:
T gradients;
T intercepts;
Line(T a, T b) : gradients(a), intercepts(b) {}
T y(T x) { return gradients * x + intercepts; }
};
vector<T> xs;
vector<Line> nodes;
int N;
int V() { return 2 * N - 1; }
// [l, r)
void insert(int i, int l, int r, Line& line) {
if (nodesi.y(xl) <= line.y(xl) && nodesi.y(xr) <= line.y(xr)) return; if (nodesi.y(xl) > line.y(xl) && nodesi.y(xr) > line.y(xr)) { return;
}
int m = (l + r) / 2;
if (line.y(xm) < nodesi.y(xm)) swap(line, nodesi); if (line.y(xl) < nodesi.y(xl)) { insert(2 * i + 1, l, m, line);
} else {
insert(2 * i + 2, m, r, line);
}
}
public:
LiChaoTree(const vector<T>& x) : xs(x) {
N = 1;
while (N < xs.size()) N <<= 1;
while (xs.size() < N) xs.push_back(xs.back() + 1);
nodes.resize(V(), Line(0, 1e32));
}
void insert(T gradients, T intercepts) {
Line line = Line(gradients, intercepts);
insert(0, 0, N, line);
}
T y(int i) {
i += N - 1;
while (i > 0) {
i = (i - 1) / 2;
res = min(res, nodesi.y(x)); }
return res;
}
};
int N;
ll C;
vector<ll> h;
int main() {
cin >> N >> C;
h.resize(N);
vector<ll> dp(N, 0);
LiChaoTree<ll> t(h);
for (int i = 1; i < N; ++i) {
int j = i - 1;
t.insert(-2LL * hj, dpj + hj * hj); dpi = t.y(i) + hi * hi + C; }
return 0;
}
参考