P4655 [CEOI2017] Building Bridges

P4655 [CEOI2017] Building Bridges

题意：

有 $n$ 根柱子，每根柱子有高度 h i h_i hi​，在柱子 $i$ 和柱子 $j$ 之间建桥的代价为 ( h i − h j ) 2 (h_i-h_j)^2 (hi​−hj​)2。每根没建桥的柱子需要花费 w i w_i wi​ 的代价拆除。询问使第 $1$ 根柱子和第 $n$ 根柱子连接的最小代价。桥不能在柱子之外的地方相交。

解析：

令 f i f_i fi​ 为使 $1$ 和 $i$ 连接的最小代价。枚举最后一座桥的起点 $j$， f i = min ⁡ j < i { f j + ∑ k = j + 1 i − 1 w k + ( h i − h j ) 2 } f_i = \\min\\limits_{j<i}\\Big\\{ f_j + \\sum\\limits_{k = j+1}\\limits^{i-1}w_k +(h_i-h_j)^2\\Big\\} fi​=j<imin​{fj​+k=j+1∑i−1​wk​+(hi​−hj​)2}

前缀和优化一下： f i = min ⁡ j < i { f j + s i − 1 − s j + ( h i − h j ) 2 } f_i = \\min\\limits_{j<i}\\Big\\{ f_j + s_{i-1}-s_j +(h_i-h_j)^2\\Big\\} fi​=j<imin​{fj​+si−1​−sj​+(hi​−hj​)2}

有 h i × h j h_i\\times h_j hi​×hj​项，可以考虑斜率优化。

整理式子： f j + h j 2 − s j = 2 h i × h j + f i − h i 2 − s i − 1 f_j+h_j^2-s_j = 2h_i\\times h_j+f_i-h_i^2-s_{i-1} fj​+hj2​−sj​=2hi​×hj​+fi​−hi2​−si−1​

y = f j + h j 2 − s j , k = 2 h i , x = h j , b = f i − h i 2 − s i − 1 y = f_j+h_j^2-s_j, k = 2h_i, x = h_j, b = f_i-h_i^2-s_{i-1} y=fj​+hj2​−sj​,k=2hi​,x=hj​,b=fi​−hi2​−si−1​

容易发现 $k$ 和 $x$ 都不单调。$x$ 的单调性影响维护凸壳的方式，$k$ 的单调性影响寻找最优决策点的方式

可以通过离线的方式解决：cdq分治！（不会平衡树维护凸包）

cdq分治中需要计算左侧对右侧的贡献。

如果左侧 $x$ 递增，则可以用单调队列维护左侧的凸壳；如果右侧斜率 $k$ 递增，则具有决策单调性。

对右侧点来说，决策点要么位于右部，要么位于左部（怎么感觉有点废话），所以cdq分治不会遗漏决策点。

1. 递归处理左侧区间
2. 单调队列维护左侧点构成的凸包
3. 对右侧区间按斜率排序，从来自左侧的决策点转移
4. 递归处理右侧区间
5. 整个区间按照 $x$ 排序

时间复杂度为 $O(n\log n)$

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define fi first
#define se second
#define debug(x) cerr << #x << ": " << (x) << endl
#define rep(i, a, b) for(int i = (a); i <= (b); i++)
const int maxn = 1e5+10;
const int maxm = 1e5+10;
const double eps = 1e-10;
const ll INF = 0x3f3f3f3f3f3f3f3f;
typedef pair<int, int> pii;int n;
ll h[maxn], s[maxn], w[maxn], dp[maxn];
int q[maxn], hh, tt;
struct node{ll k, x, y, id;bool operator < (const node &b) const{if(x != b.x)return x < b.x;elsereturn y < b.y;}
}a[maxn], tmp[maxn];
bool cmp(node a, node b){return a.k < b.k;
}
long double slope(int i, int j){long double x1 = (long double)a[i].x;long double y1 = (long double)a[i].y;long double x2 = (long double)a[j].x;long double y2 = (long double)a[j].y;if(fabs(x2-x1) < eps)return y2 > y1 ? 1e18 : -1e18;elsereturn (y2-y1)/(x2-x1);
}
void cdq(int l, int r){if(l == r){int j = a[l].id;a[l].y = dp[j] + h[j]*h[j] - s[j];return; }int mid = (l+r) >> 1;int p1 = l, p2 = mid+1;for(int i = l; i <= r; i++){if(a[i].id <= mid)tmp[p1++] = a[i];elsetmp[p2++] = a[i];}for(int i = l; i <= r; i++)a[i] = tmp[i];cdq(l, mid);hh = 1, tt = 0;for(int i = l; i <= mid; i++){while(hh < tt && slope(q[tt-1], q[tt]) >= slope(q[tt], i))tt--;q[++tt] = i;}for(int i = mid+1; i <= r; i++){while(hh < tt && slope(q[hh], q[hh+1]) <= a[i].k)hh++;if(hh <= tt){int j = q[hh];int id = a[i].id;dp[id] = min(dp[id], a[j].y - a[i].k*a[j].x + s[id-1]+ h[id]*h[id]);} }cdq(mid+1, r);p1 = l, p2 = mid+1;int p = l;while(p1 <= mid && p2 <= r){if(a[p1] < a[p2])tmp[p++] = a[p1++];elsetmp[p++] = a[p2++];}while(p1 <= mid)tmp[p++] = a[p1++];while(p2 <= r)tmp[p++] = a[p2++];for(int i = l; i <= r; i++)a[i] = tmp[i];
}
int main(){ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);cin >> n;for(int i = 1; i <= n; i++)cin >> h[i];for(int i = 1; i <= n; i++){cin >> w[i];s[i] = s[i-1] + w[i];}for(int i = 1; i <= n; i++){a[i].k = 2ll * h[i];a[i].x = h[i];a[i].id = i;}memset(dp, INF, sizeof(dp));dp[1] = 0;sort(a+1, a+1+n, cmp);cdq(1, n);cout << dp[n] << endl;return 0;
}