P4655 [CEOI2017] Building Bridges

题意

思路

设 \(sum_i = \sum\limits_{j = 1}^i w_j\)。

可以得到转移方程 \(f_i = f_j + (h_i - h_j) ^ 2 + sum_i - sum_j\)。

转化为 \(y = kx + b\) 的形式：

\(f_i = f_j + (h_i - h_j) ^ 2 + sum_i - sum_j = f_j + h_i^2 + h_j^2 - 2 h_ih_j + sum_i - sum_j = (-2h_ih_j) + (f_j + h_j ^ 2 - sum_j) + (h_i ^ 2 + sum_i)\)。

转化完成，\(k = -2h_i, b = f_j + h_j ^ 2 - sum_j\)。

然后我们边转移，边把这条线段放入即可。

代码

#include <bits/stdc++.h>#define int long longusing namespace std;const int N = 1000010;int n, h[N], w[N], f[N];struct node {int id;
} tr[N << 2];double gety(double k, int x, double b) {return k * x + b;
}double k[N], b[N];bool compare(int v1, int v2, int x) {double y1 = gety(k[v1], x, b[v1]);double y2 = gety(k[v2], x, b[v2]);return y1 < y2;
}void update(int u, int l, int r, int pl, int pr, int x) {int mid = l + r >> 1;if (pl <= l && r <= pr) {if (!tr[u].id) {tr[u].id = x;return;}if (compare(x, tr[u].id, mid)) swap(tr[u].id, x);if (compare(x, tr[u].id, l)) update(u << 1, l, mid, pl, pr, x);if (compare(x, tr[u].id, r)) update(u << 1 | 1, mid + 1, r, pl, pr, x);return;}if (pl <= mid) update(u << 1, l, mid, pl, pr, x);if (pr > mid) update(u << 1 | 1, mid + 1, r, pl, pr, x);
}double query(int u, int l, int r, int x) {if (l == r) return gety(k[tr[u].id], x, b[tr[u].id]);int mid = l + r >> 1;double ans = gety(k[tr[u].id], x, b[tr[u].id]), ans2 = 0;if (x <= mid) ans2 = query(u << 1, l, mid, x);else ans2 = query(u << 1 | 1, mid + 1, r, x);return min(ans, ans2);
}signed main() {ios::sync_with_stdio(false);cin.tie(nullptr);cin >> n;for (int i = 1; i <= n; i++ )cin >> h[i];for (int i = 1; i <= n; i++) cin >> w[i], w[i] += w[i - 1];b[0] = 1e18;k[1] = -2 * h[1], b[1] = h[1] * h[1] - w[1];update(1, 1, 1000000, 1, 1000000, 1);for (int i = 2; i <= n; i++) {f[i] = h[i] * h[i] + w[i - 1] + query(1, 1, 1000000, h[i]);k[i] = -2 * h[i], b[i] = f[i] + h[i] * h[i] - w[i];update(1, 1, 1000000, 1, 1000000, i);}cout << f[n] << '\n';return 0;
}