loj#2483. 「CEOI2017」Building Bridges 斜率优化 cdq分治

loj#2483. 「CEOI2017」Building Bridges

链接

https://loj.ac/problem/2483

思路

\[f[i]=f[j]+(h[i]-h[j])^2+(sum[i-1]-sum[j])
\]

\[f[i]=f[j]+h[i]^2+h[j]^2-2*h[i]*h[j]+sum[i-1]-sum[j]
\]

\[sum[j]-f[j]-h[j]^2=(-2*h[j])*h[i]+sum[i-1]+h[i]^2-f[i]
\]

\[f[j]+h[j]^2-sum[j]=2*h[j]*h[i]-sum[i-1]-h[i]^2+f[i]
\]

\[x=h[j],y=f[j]+h[j]^2-sum[j]
\]

\[k=2*h[i],b=没用
\]

然后cdq维护一下凸包

细节

首先按照k排序(k是已知的)，保证询问不再二分凸包(\(log^2n\))而是使用单调队列(\(logn\))。

计算斜率的函数一定要写好了。

还有最后按照x排序的函数也要一起写好。

会受影响的

大体流程

if(l==r) return;

按照mid把p分成两半

cdq(l,mid)

建立左边的凸包

左边的凸包更新右边的答案

cdq(mid+1,r)

按照x排序p

ps:p就是个结构体存很多东西

代码

#include <bits/stdc++.h>

#define ll long long

using namespace std;

const ll N=2e5+7;

const ll inf=0x3f3f3f3f3f3f3f3f;

ll read() {

	ll x=0,f=1;char s=getchar();

	for(;s>'9'||s<'0';s=getchar()) if(s=='-') f=-1;

	for(;s>='0'&&s<='9';s=getchar()) x=x*10+s-'0';

	return x*f;

}

ll n,h[N],sum[N],f[N];

struct node {

	ll k,x,y,id;

	bool operator < (const node &b) const {

		return k<b.k;

	}

}q[N],t[N];

ll stak[N],top;

double get_k(ll a,ll b) {

	if(!b) return inf;

	if(q[a].x==q[b].x) return q[a].y<=q[b].y?inf:-inf;

	return 1.0*(q[a].y-q[b].y)/(q[a].x-q[b].x);

}

void solve(ll l,ll r) {

	if(l==r) {

		q[l].y=f[l]+h[l]*h[l]-sum[l];

		return;

	}

	ll mid=(l+r)>>1,l1=l,l2=mid+1;

	//sort q according to id

	for(ll i=l;i<=r;++i) {

		if(q[i].id<=mid) t[l1++]=q[i];

		else t[l2++]=q[i];

	}

	for(ll i=l;i<=r;++i) q[i]=t[i];

	solve(l,mid);

	//build a convex hull on the left

	top=0;

	for(ll i=l;i<=mid;++i) {

		while(top>1&&get_k(stak[top-1],stak[top])>get_k(stak[top-1],i)) top--;

		stak[++top]=i;

	}

	stak[++top]=0;

	//update ans on the right

	for(ll dsr=mid+1,DSR=1;dsr<=r;++dsr) {

		while(DSR<top&&get_k(stak[DSR],stak[DSR+1])<q[dsr].k)

			DSR++;

		ll i=q[dsr].id,j=q[stak[DSR]].id;

		f[i]=min(f[i],f[j]+(h[i]-h[j])*(h[i]-h[j])+sum[i-1]-sum[j]);

	}

	solve(mid+1,r);

	//sort q according to x

	l1=l,l2=mid+1;

	for(ll i=l;i<=r;++i) {

		if(((q[l1].x<q[l2].x||(q[l1].x==q[l2].x&&q[l1].y<q[l2].y)||l2>r))&&l1<=mid) t[i]=q[l1++];

		// if(((p[l1].x<p[l2].x||(fabs(p[l1].x-p[l2].x)<eps&&p[l1].y<p[l2].y)||l2>r))&&l1<=mid)

		else t[i]=q[l2++];

	}

	for(ll i=l;i<=r;++i) q[i]=t[i];

}

int main() {

	n=read();

	for(ll i=1;i<=n;++i) h[i]=read();

	for(ll i=1;i<=n;++i) sum[i]=sum[i-1]+read();

	for(ll i=1;i<=n;++i) q[i].x=h[i],q[i].k=2*h[i],q[i].id=i;

	memset(f,0x3f,sizeof(f));f[1]=0;

	sort(q+1,q+1+n);

	solve(1,n);

	printf("%lld\n",f[n]);

	return 0;

}

巴特西

loj#2483. 「CEOI2017」Building Bridges 斜率优化 cdq分治

链接

思路

细节

大体流程

代码

最新文章

热门文章