题解 P4655 【[CEOI2017]Building Bridges】
GKxx
2019-05-03 23:02:47
设$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;
}