题解 P4655 【[CEOI2017]Building Bridges】

设$s_i$为$w_i$的前缀和，$f_i$表示将第$1$根柱子与第$i$根柱子连接的最小代价。考虑最后一座桥从第$j$根柱子架到第$i$根柱子，于是枚举$j$，有转移 $$f_i=\min\{f_j+s_{i-1}-s_j+(h_i-h_j)^2\}$$ 把平方展开，提出仅与$i$有关的项 $$f_i=\min\{f_j-s_j+h_j^2-2h_ih_j\}+s_{i-1}+h_i^2$$ 设$y_i=f_i-s_i+h_i^2,x_i=h_i,k_i=2h_i$，那么 $$f_i=\min\{y_j-k_ix_j\}+s_{i-1}+h_i^2$$ 是比较显然的斜率优化。由于这里斜率和横坐标都不单调，不能简单用单调队列解决。可以使用splay维护动态凸包。 这里斜率是正的，要最小化截距，我们需要维护下凸壳。 在splay上维护目前的下凸壳上的结点，结点横坐标从小到大的顺序即为splay中序遍历的顺序。 在splay上对每个节点$x$记录$\mathrm{lk}_x$和$\mathrm{rk}_x$两个值，分别代表在凸壳上$x$左侧那个点与它的连线的斜率（不妨称为“左线斜率”）和它右侧那个点与它连线的斜率（不妨称为“右线斜率”）。 我们可以在splay上二分来找到对于$i$的最优决策点$j$进行转移。对于当前节点$x$： - 如果$\mathrm{lk}_x\leq k_i\leq\mathrm{rk}_x$，说明这条直线在这里与凸壳相切，这个点$x$就是最优决策点。 - 如果$k_i<\mathrm{lk}_x$，说明切点在左侧，对左子树递归调用。 - 如果$k_i>\mathrm{rk}_x$，说明切点在右侧，对右子树递归调用。 求出$f_i$之后要将这个点插入平衡树。首先按横坐标递增顺序找到它的插入位置，插入这个结点并splay到根。然后检查它左右的结点，把由于它的插入而不满足凸包性质的点删除，同时求出它的左右线斜率。最后检查如果它的左线斜率大于右线斜率，说明这个结点不在凸壳上，将它删除。 两个注意点：$f_1$和$f_2$要单独拎出来写，还有注意斜率不存在的情况。 类似的题目可以看看NOI2007的货币兑换 ```cpp #include <cctype> #include <cstdio> #include <climits> #include <algorithm> #include <cmath> template <typename T> inline void read(T& x) { int f = 0, c = getchar(); x = 0; while (!isdigit(c)) f |= c == '-', c = getchar(); while (isdigit(c)) x = x * 10 + c - 48, c = getchar(); if (f) x = -x; } template <typename T, typename... Args> inline void read(T& x, Args&... args) { read(x); read(args...); } template <typename T> void write(T x) { if (x < 0) x = -x, putchar('-'); if (x > 9) write(x / 10); putchar(x % 10 + 48); } template <typename T> inline void writeln(T x) { write(x); puts(""); } template <typename T> inline bool chkmin(T& x, const T& y) { return y < x ? (x = y, true) : false; } template <typename T> inline bool chkmax(T& x, const T& y) { return x < y ? (x = y, true) : false; } typedef long long LL; const int maxn = 1e5 + 207; const double inf = 1e16, eps = 1e-10; LL s[maxn], h[maxn], f[maxn]; double lk[maxn], rk[maxn], xc[maxn], yc[maxn]; int ch[maxn][2], fa[maxn], root; int n; inline double slope(int i, int j) { if (fabs(xc[i] - xc[j]) <= eps) return yc[i] < yc[j] ? inf : -inf; return (yc[i] - yc[j]) / (xc[i] - xc[j]); } inline int iden(int x) { return ch[fa[x]][0] == x ? 0 : (ch[fa[x]][1] == x ? 1 : -1); } inline void rotate(int x) { int d = iden(x), y = fa[x]; if (~iden(y)) ch[fa[y]][iden(y)] = x; fa[x] = fa[y]; if ((ch[y][d] = ch[x][d ^ 1])) fa[ch[x][d ^ 1]] = y; fa[ch[x][d ^ 1] = y] = x; } inline void splay(int x, int &k) { if (x == k) return; for (int p = fa[k], y = fa[x]; y != p; y = fa[x]) { if (fa[y] != p) rotate(iden(y) ^ iden(x) ? x : y); rotate(x); } k = x; } int queryBest(int x, double k) { if (!x) return 0; if (lk[x] <= k + eps && k <= rk[x] + eps) return x; if (k + eps >= rk[x]) return queryBest(ch[x][1], k); else return queryBest(ch[x][0], k); } inline int getPrev(int x) { int ans = 0; for (int y = ch[x][0]; y;) { if (lk[y] <= slope(y, x) + eps) ans = y, y = ch[y][1]; else y = ch[y][0]; } return ans; } inline int getNext(int x) { int ans = 0; for (int y = ch[x][1]; y;) { if (slope(x, y) <= rk[y] + eps) ans = y, y = ch[y][0]; else y = ch[y][1]; } return ans; } inline void update(int &rt, int x) { splay(x, rt); if (ch[x][0]) { int y = getPrev(x); splay(y, ch[x][0]); ch[y][1] = 0; rk[y] = lk[x] = slope(y, x); } else lk[x] = -inf; if (ch[x][1]) { int y = getNext(x); splay(y, ch[x][1]); ch[y][0] = 0; rk[x] = lk[y] = slope(x, y); } else rk[x] = inf; if (lk[x] + eps >= rk[x]) { rt = ch[x][0]; fa[ch[rt][1] = ch[x][1]] = rt; fa[rt] = 0; rk[rt] = lk[ch[rt][1]] = slope(rt, ch[rt][1]); } } void insert(int &x, int dad, int id) { if (!x) { fa[x = id] = dad; return; } insert(xc[x] <= xc[id] + eps ? ch[x][1] : ch[x][0], x, id); } int main() { read(n); for (int i = 1; i <= n; ++i) read(h[i]); for (int i = 1, x; i <= n; ++i) read(x), s[i] = s[i - 1] + x; f[1] = 0; xc[1] = h[1]; yc[1] = f[1] - s[1] + 1.0 * h[1] * h[1]; f[2] = 1ll * (h[2] - h[1]) * (h[2] - h[1]); xc[2] = h[2]; yc[2] = f[2] - s[2] + 1.0 * h[2] * h[2]; insert(root, 0, 1); update(root, 1); insert(root, 0, 2); update(root, 2); for (int i = 3; i <= n; ++i) { int j = queryBest(root, 2 * h[i]); f[i] = f[j] + s[i - 1] - s[j] + (h[i] - h[j]) * (h[i] - h[j]); xc[i] = h[i]; yc[i] = f[i] - s[i] + 1.0 * h[i] * h[i]; insert(root, 0, i); update(root, i); } writeln(f[n]); return 0; }