P4655 [CEOI2017] Building Bridges

pengchujie / 2023-08-26 / 原文

传送门

考虑朴素做法：\(f_i\)表示通过桥架把第\(1\)根和第\(i\)根柱子连接的最小费用
，\(g_{i,j}\)表示用桥梁连接\(i\)和\(j\)的最小费用，\(s_i=\sum\limits_{j=1}^i{w_j}\)

\[\begin{cases}g_{i,j}=f_j+s_{i-1}-s_j+(h_i-h_j)^2\\f_i=\min\limits_{j=1}^{i-1}g_{i,j}\end{cases} \]

考虑斜率优化\(DP\)：

考虑\(j_1<j_2,g_{i,j_2}<g_{i,j_1}\)的情况

此时应满足：

\[f_{j_2}+s_{i-1}-s_{j_2}+{h_i}^2-2h_ih_{j_2}+{h_{j_2}}^2<f_{j_1}+s_{i-1}-s_{j_1}+{h_i}^2-2h_ih_{j_1}+{h_{j_1}}^2 \]

令\(y_i=f_i-s_i+{h_i}^2\)，化简得：

\[y_{j_2}-y_{j_1}<2h_i(h_{j_2}-h_{j_1}) \]

然而我们发现一个问题：\(h_{j_2}-h_{j_1}\)不一定大于\(0\)，但小于等于\(0\)又会导致两边不能同时除\(h_{j_2}-h_{j_1}\)，否则会导致不等式变号

考虑分治维护：

定义一个结构体\(a[i]\)，\(a[i].x=h_i,a[i].y=y_i,a[i].wz=i\)

因为对于\(i<j\)，\(f_j\)不会对\(f_i\)产生任何影响但\(f_i\)会对\(f_j\)产生影响。

那么对于区间\([l,r]\)，我们可以这么处理：

若\(l=r\)，则直接返回

若\(l<r\)，则令\(mid=(l+r)/2\)，将区间\([l,r]\)分成\([l,mid]\)和\([mid+1,r]\)递归先处理\([l,mid]\)的部分（不必管\([l,mid]\)怎么求，只要我们可以求出\([l,r]\)，又有边界条件，就可以求出\([l,mid]\)，毕竟是分治）。

将\(a[l,mid]\)和\(a[mid+1,r]\)排序，先按照\(a[i].x\)从小到大排，若\(a[i].x\)相同，则按\(a[i].y\)从小到大排（看上面那条式子，排序之后既保证了\((h_{j_2}-h_{j_1})\ge0\)又保证了\(h_i\)单调递增）

然后直接斜率优化\(DP\)用左边的\(f_j\)去更新右边的\(f_i\)，在递归处理\([mid+1,r]\)部分

细节再代码中体现，上代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=1e5+50;
ll n,f[N],w[N];
struct jgt
{
	ll x,y,wz;
}a[N],b[N];
ll he,ta,q[N],s[N],h[N];
ll y(ll i){return f[i]-s[i]+h[i]*h[i];}
bool cmp(jgt t1,jgt t2)
{
	return t1.x<t2.x;
}
void CDQ(ll l,ll r)
{
	if(l==r)
	{
		a[l].y=y(l);
		return ;
	}
	ll mid=(l+r)/2;
	ll t1=l,t2=mid+1;
	for(ll i=l;i<=r;i++)
	if(a[i].wz<=mid) b[t1++]=a[i];
	else b[t2++]=a[i];
	for(ll i=l;i<=r;i++)
	a[i]=b[i];
	CDQ(l,mid);
	he=1,ta=0;
	for(ll i=l;i<=mid;i++)
	{
		if(i>l&&a[i].x==a[i-1].x) continue;
		while(he<ta&&(a[i].y-a[q[ta]].y)*(a[q[ta]].x-a[q[ta-1]].x)<=(a[q[ta]].y-a[q[ta-1]].y)*(a[i].x-a[q[ta]].x)) ta--;
		q[++ta]=i;
	}
	for(ll i=mid+1;i<=r;i++)
	{
		while(he<ta&&a[q[he+1]].y-a[q[he]].y<=2*a[i].x*(a[q[he+1]].x-a[q[he]].x)) he++;
		ll u=a[i].wz,v=a[q[he]].wz;
		f[u]=min(f[u],f[v]+s[u-1]-s[v]+(h[u]-h[v])*(h[u]-h[v]));
	}
	CDQ(mid+1,r);
	t1=l,t2=mid+1;
	ll t3=l;
	while(t1<=mid&&t2<=r)
		if(a[t1].x<a[t2].x||(a[t1].x==a[t2].x&&a[t1].y<a[t2].y)) b[t3]=a[t1],t1++,t3++;
		else b[t3]=a[t2],t2++,t3++;
	while(t1<=mid)
		b[t3]=a[t1],t1++,t3++;
	while(t2<=r)
		b[t3]=a[t2],t2++,t3++;
	for(ll i=l;i<=r;i++)
		a[i]=b[i];
}
int main()
{
	scanf("%lld",&n);
	for(ll i=1;i<=n;i++)
	{
		scanf("%lld",&h[i]);
		a[i].x=h[i];
	}
	for(ll i=1;i<=n;i++)
	{
		scanf("%lld",&w[i]);
		a[i].wz=i;
		s[i]=s[i-1]+w[i];
	}
	for(int i=2;i<=n;i++)
		f[i]=1e16;
	sort(a+1,a+n+1,cmp);
	CDQ(1,n); 
	printf("%lld\n",f[n]);
	return 0;
}