Luogu4655 [CEOI2017]Building Bridges
斜率优化，cdq分治
考虑计算所有拆除柱子的贡献，再在转移过程中消去
于是得到一个状态转移方程
\[f_i=\begin{cases}\displaystyle\sum_{i=2}^n w_i&(i=1)\\\displaystyle\min\{f_j+(h_i-h_j)^2-w_i\}&(i>1)\end{cases}
\]
\]
答案即为 \(f_n\)
于是就有了一个优秀的 \(O(n^2)\) 的过不去算法了
然而这玩意儿是可以斜率优化的
通过一番套路地化式子，可以得到
\[f_j+h_j^2=2h_ih_j+f_i-h_i^2+w_i
\]
\]
令 \(h_j\) 为横坐标， \(f_j+h_j^2\) 为纵坐标， \(2h_i\) 为斜率
然后……可以发现 \(h_j\) 不是递增的……
这就意味着……需要支持插入，询问前驱后继，以及一些复杂的分类讨论……
我会平衡树维护动态凸包！
然而有更好的离线解决办法：cdq分治
强制让斜率递增然后计算贡献
回想cdq分治的过程，左右递归，计算左侧对右侧的贡献
如果左侧斜率递增，并且左侧编号小于右侧，那么可以通过单调队列维护左侧的凸包来更新右侧答案
并且这样一定能够遍历出每个节点的所有决策点
注意 \(long\ long\) ，以及求斜率时 \(x_1=x_2\) 的情况
时间复杂度 \(O(n\log n)\)
代码
#include <bits/stdc++.h>
using namespace std;
typedef double db;
typedef long long ll;
const int maxn = 1e5 + 10;
ll f[maxn];
int n, w[maxn];
struct node {
int x, tid; ll y;
} a[maxn], dat[maxn];
ll sqr(ll x) { return x * x; }
db slope(int x, int y) {
if (a[x].x == a[y].x) {
return a[x].y < a[y].y ? 1e18 : -1e18;
}
return db(a[x].y - a[y].y) / db(a[x].x - a[y].x);
}
void cdq(int l, int r) {
if (l == r) {
a[l].y = f[a[l].tid] + sqr(a[l].x);
return;
}
int mid = (l + r) >> 1;
for (int i = l, p1 = l, p2 = mid + 1; i <= r; i++) {
if (a[i].tid <= mid) {
dat[p1++] = a[i];
} else {
dat[p2++] = a[i];
}
}
for (int i = l; i <= r; i++) {
a[i] = dat[i];
}
cdq(l, mid);
int L = 1, R = 0;
static int q[maxn];
for (int i = l; i <= mid; i++) {
while (L < R && slope(q[R - 1], q[R]) > slope(q[R], i)) R--;
q[++R] = i;
}
for (int i = mid + 1; i <= r; i++) {
while (L < R && slope(q[L], q[L + 1]) < 2 * a[i].x) L++;
int x = a[i].tid, y = a[q[L]].tid;
f[x] = min(f[x], f[y] + sqr(a[i].x - a[q[L]].x) - w[x]);
}
cdq(mid + 1, r);
for (int i = l, p1 = l, p2 = mid + 1; i <= r; i++) {
if (p2 > r || (p1 <= mid && a[p1].x < a[p2].x)) {
dat[i] = a[p1++];
} else {
dat[i] = a[p2++];
}
}
for (int i = l; i <= r; i++) {
a[i] = dat[i];
}
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i].x);
a[i].tid = i, f[i] = 1ll << 60;
}
f[1] = 0;
for (int i = 1; i <= n; i++) {
scanf("%d", w + i);
if (i > 1) f[1] += w[i];
}
sort(a + 1, a + n + 1, [](node a, node b) {
return a.x < b.x;
});
cdq(1, n);
printf("%lld", f[n]);
return 0;
}
2019.4.30 upd: 我发现这玩意儿好像是WC2013被提出来的……