题目传送门：。
题意简述：
有 \(n\) 个数，每个数有高度 \(h_i\) 和价格 \(w_i\) 两个属性。
你可以花费 \(w_i\) 的代价移除第 \(i\) 个数（不能移除第 \(1\) 个和第 \(n\) 个数）。
这之后，没有被移除的数中，相邻两个数 \(i\) 和 \(j\) 会产生 \((h_j-h_i)^2\) 的代价。
求最小代价。
题解：
斜率优化 DP。
考虑 \(\mathrm{f}[i]\) 表示只考虑前 \(i\) 个数的最小代价，易得转移 \(\displaystyle\mathrm{f}[i]=\min_{j=1}^{i-1}(\mathrm{f}[j]+(h_i-h_j)^2+s_{i-1}-s_j)\)。
其中 \(s_n\) 表示 \(\displaystyle\sum_{i=1}^{n}w_i\)。
简化式子：\(\displaystyle\mathrm{f}[i]=h_i^2+s_{i-1}+\min_{j=1}^{i-1}(\mathrm{f}[j]+h_j^2-s_j-2h_ih_j)\)。显然可以看出斜率优化的形式。
考虑两个合法转移点 \(j\) 和 \(k\)，比较 \(j\) 和 \(k\) 转移的优劣：
\[\begin{aligned}\mathrm{f}[j]+h_j^2-s_j-2h_i\times h_j&\Leftrightarrow\mathrm{f}[k]+h_k^2-s_k-2h_i\times h_k\\(\mathrm{f}[k]+h_k^2-s_k)-(\mathrm{f}[j]+h_j^2-s_j)&\Leftrightarrow 2h_i\times(h_k-h_j)\end{aligned}\]
\(x\) 坐标是 \(h_i\)，\(y\) 坐标是 \(\mathrm{f}[i]+h_i^2-s_i\)。假设 \(x_j<x_k\)，则决策 \(j\) 比 \(k\) 优当且仅当：
\[\begin{aligned}\mathrm{f}[j]+h_j^2-s_j-2h_i\times h_j&<\mathrm{f}[k]+h_k^2-s_k-2h_i\times h_k\\y_k-y_j&>2h_i\times(x_k-x_j)\\\frac{y_k-y_j}{x_k-x_j}&>2h_i\end{aligned}\]
即点 \((x_j,y_j)\) 和点 \((x_k,y_k)\) 之间的线段的斜率大于 \(2h_i\)。
因为 \(x_i=h_i\) 不单调，所以需要动态维护下凸壳，这可以通过使用平衡树维护解决，复杂度 \(\mathcal{O}(n\log n)\)。
也可以使用 CDQ 分治的方法解决，分治左半边后考虑按照 \(h_i\) 排序，使用单调队列在线性复杂度内得到下凸壳，以及线性更新答案。
这里的排序可以使用归并排序，不会提高复杂度，但是我为了方便直接使用了快速排序，时间复杂度 \(\mathrm{O}(n\log^2n)\)。
#include#include #include typedef long long LL;const int MN = 100005;int N, p[MN], tmp[MN];LL h[MN], w[MN], f[MN], X[MN], Y[MN];inline double Slope(int i, int j) { if (X[i] == X[j]) return 1e50 * (Y[j] - Y[i]); return (double)(Y[j] - Y[i]) / (X[j] - X[i]);}int que[MN], l, r;void Solve(int lb, int rb) { if (lb == rb) { Y[lb] += f[lb]; return ; } int mid = (lb + rb) >> 1; Solve(lb, mid); for (int i = lb; i <= rb; ++i) p[i] = i; std::sort(p + lb, p + rb + 1, [](int i, int j) { return h[i] < h[j]; }); l = 1, r = 0; for (int i = lb; i <= rb; ++i) if (p[i] <= mid) { while (l < r && Slope(que[r - 1], que[r]) >= Slope(que[r], p[i])) --r; que[++r] = p[i]; } for (int i = lb; i <= rb; ++i) if (p[i] > mid) { while (l < r && Slope(que[l], que[l + 1]) <= 2 * h[p[i]]) ++l; f[p[i]] = std::min(f[p[i]], f[que[l]] + (h[p[i]] - h[que[l]]) * (h[p[i]] - h[que[l]]) + w[p[i] - 1] - w[que[l]]); } Solve(mid + 1, rb);}int main() { scanf("%d", &N); for (int i = 1; i <= N; ++i) scanf("%lld", &h[i]); for (int i = 1; i <= N; ++i) scanf("%lld", &w[i]), w[i] += w[i - 1]; for (int i = 1; i <= N; ++i) p[i] = i, X[i] = h[i], Y[i] = h[i] * h[i] - w[i]; memset(f, 0x7f, sizeof f); f[1] = 0, Solve(1, N); printf("%lld\n", f[N]); return 0;}