目录
@desription@
有 n 根柱子依次排列，第 i 根柱子的高度为 hi 。现可以花费 (hi - hj)^2 的代价建桥架在第 i 根柱子和第 j 根柱子之间。
所有用不到的柱子都会被拆除，第 i 根柱子被拆除的代价为 wi 。 求用桥把第 1 根柱子和第 n 根柱子连接的最小代价。注意桥梁不能在端点以外的任何地方相交。input
第一行一个正整数 n。 2 <= n <= 10^5。 第二行 n 个空格隔开的整数，依次表示 h1, h2, ..., hn。0 <= hi <= 10^6。 第三行 n 个空格隔开的整数，依次表示 w1, w2, ..., wn。0 <= |wi| <= 10^6。output
输出一个整数表示最小代价，注意最小代价不一定是正数。sample input
6 3 8 7 1 6 6 0 -1 9 1 2 0sample output 17@solution@
一个很 naive 的 dp：定义状态 \(dp[i]\) 表示将 1 与 i 连接起来的最小费用，并再定义一个前缀和 \(s[i] = \sum_{p=1}^{i}w[p]\)，则状态转移为：
\[dp[i]=min\{dp[j]+s[i]-s[j]+(h[i]-h[j])^2\}\] 满脸的斜率优化。横坐标为 \(x[j] = h[j]\)，纵坐标为\(y[j] = dp[j] - s[j] + h[j]^2\)，斜率为 \(k[i] = 2*h[i]\)，只和 i 有关的常数 \(c[i] = s[i] + h[i]^2\)。
转移式变为：\[dp[i]=min\{c[i]+y[j]-k[i]*x[j]\}\]然而……斜率不单调就算了……TM 横坐标也不单调。
对于这种题，一是写平衡树，一是用 cdq 分治。 因为感性描述一下我们的思想：我们把区间分为两部分，左半部分依照横坐标排序，右半部分依照斜率排序，同时保证左半部分所有的编号小于右半部分所有的编号。
在这个前提下，用左边去更新右边，就是一个简单的单调栈问题了。我们当然不可能在每一层都去排一下序什么的，这样时间复杂度就退化成 O(nlog^2n) 的。
所以我们的解决方法是这样的： 首先我们把所有点按照斜率来排序，开始递归区间 [1, n]。 对于当前这一层 [l, r]，将这些点按照编号与 mid 的关系，分成左右两部分，同时两部分内部都保持斜率单调的顺序。因为我们一开始递归的是 [1, n]，按照上面这一套方法，递归 [l, r] 的时候这个区间内所有点的编号都在 [l, r] 范围内。 然后，先递归 [l, mid]，求出这段区间的 dp 值，并在递归时以它们的横坐标为关键字进行排序（归并排序）。 再一套单调栈更新右半部分。递归 [mid, r] 求解。此时左右两部分都是以横坐标为关键字的有序状态。 在最后归并即可。好像有些冗长……最好看一看代码确认一下细节。
@accepted code@
#include#include using namespace std;typedef long long ll;const int MAXN = 100000;const ll INF = (1LL<<62);struct node{ ll w, h, c, k, x, y, dp; int pos;}a[MAXN + 5], tmp[MAXN + 5], que[MAXN + 5];bool cmp(node a, node b) { return a.k < b.k;}void cdq(int le, int ri) { if( le == ri ) { a[le].x = a[le].h; a[le].y = a[le].h*a[le].h + a[le].dp - a[le].w; return ; } int mid = (le + ri) >> 1, p = le, q = mid + 1, r = le; for(r = le;r <= ri;r++) if( a[r].pos <= mid ) tmp[p++] = a[r]; else tmp[q++] = a[r]; for(r = le;r <= ri;r++) a[r] = tmp[r]; cdq(le, mid); int s = 1, t = 0; for(p = le;p <= mid;p++) { while( s < t && (que[t].y - que[t-1].y)*(a[p].x - que[t].x) >= (a[p].y - que[t].y)*(que[t].x - que[t-1].x) ) t--; que[++t] = a[p]; } for(q = mid + 1;q <= ri;q++) { while( s < t && a[q].k*(que[s+1].x - que[s].x) >= (que[s+1].y - que[s].y) ) s++; a[q].dp = min(a[q].dp, a[q].c + que[s].y - que[s].x*a[q].k); } cdq(mid + 1, ri); p = le, q = mid + 1, r = le; while( p <= mid && q <= ri ) { if( a[p].x == a[q].x ) tmp[r++] = (a[p].y < a[q].y) ? a[p++] : a[q++]; else tmp[r++] = (a[p].x < a[q].x) ? a[p++] : a[q++]; } while( p <= mid ) tmp[r++] = a[p++]; while( q <= ri ) tmp[r++] = a[q++]; for(r = le;r <= ri;r++) a[r] = tmp[r];}int main() { int n; scanf("%d", &n); for(int i=1;i<=n;i++) scanf("%lld", &a[i].h), a[i].pos = i; for(int i=1;i<=n;i++) scanf("%lld", &a[i].w), a[i].w += a[i-1].w; for(int i=1;i<=n;i++) a[i].k = 2*a[i].h, a[i].c = a[i].h*a[i].h + a[i-1].w, a[i].dp = INF; a[1].dp = 0; sort(a+1, a+n+1, cmp); cdq(1, n); for(int i=1;i<=n;i++) if( a[i].pos == n ) printf("%lld\n", a[i].dp);}
@details@
cdq 分治真的太巧妙了。
我们需要维护三部分的有序性：斜率，横坐标，编号。 你看 cdq 分治，只需要一点点离线化，就可以顺利解决这三部分的矛盾。巧妙，太巧妙了。