LOJ #2483 [CEOI2017]Building Bridges CDQ分治+斜率优化

本文主要是介绍LOJ #2483 [CEOI2017]Building Bridges CDQ分治+斜率优化，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：传送门
洛咕传送门

令 $s u m w$ 表示 $w$ 的前缀和。
显然的 $d p$ 方程： $dp[i]=min(dp[j]+(h[i]-h[j])^2+sumw[i-1]-sumw[j])$
展开，移项，~~一通乱搞~~，得到 $2h[i]*h[j]+dp[i]+常数=dp[j]+h[j]^2-sumw[j]$
有乘积项，所以要斜率优化。
发现 $h$ 不单调，所以需要CDQ分治。
然后就是CDQ分治+斜率优化的套路：
先把所有点按照 $x$ 坐标排序（本题 $x$ 坐标为 $h$ ），然后CDQ分治时把 $i d$ 在 $[l, m i d]$ 和 $[m i d + 1, r]$ 的分成左右两边区间，这样仍然满足左边和右边区间 $x$ 坐标分别单调。
然后套上单调队列+斜率优化即可qwq。

代码

#include<stdio.h>
#include<cstring>
#include<algorithm>
#define re register int
#define rl register ll
using namespace std;
typedef long long ll;
int read() {re x=0,f=1;char ch=getchar();while(ch<'0' || ch>'9') {if(ch=='-')    f=-1;ch=getchar();}while(ch>='0' && ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;
}
inline void write(int x) {if(x>9)	write(x/10);putchar(x%10+'0');
}
const int Size=100005;
namespace I_Love {ll n,h[Size],w[Size],sumw[Size],dp[Size];
struct node {double x,y;int id;
} p[Size],tmp[Size],Queue[Size];
inline bool comp(node a,node b) {if(a.x!=b.x)	return a.x<b.x;return a.id<b.id;
}
inline bool operator < (node a,node b) {return a.x<b.x;
}
void Divide(int l,int r) {int mid=(l+r)>>1;int ptrl=l-1,ptrr=mid;for(re i=l; i<=r; i++) {if(p[i].id<=mid) {tmp[++ptrl]=p[i];} else {tmp[++ptrr]=p[i];}}for(re i=l; i<=r; i++) {p[i]=tmp[i];}
}
void Merge(int l,int r) {int mid=(l+r)>>1;int ptrl=l,ptrr=mid+1,tot=l-1;while(ptrl<=mid && ptrr<=r) {if(p[ptrl]<p[ptrr]) {tmp[++tot]=p[ptrl++];} else {tmp[++tot]=p[ptrr++];}}while(ptrl<=mid)	tmp[++tot]=p[ptrl++];while(ptrr<=r)		tmp[++tot]=p[ptrr++];for(re i=l; i<=r; i++) {p[i]=tmp[i];}
}
inline double slope(node a,node b) {return (b.y-a.y)/(b.x-a.x);
}
void CDQ_Divide(int l,int r) {if(l==r) {p[l].y=dp[l]+h[l]*h[l]-sumw[l];return;}int mid=(l+r)>>1;//按照id分为左右两个区间 Divide(l,r);CDQ_Divide(l,mid);int hd=1,tl=0;//斜率优化 for(re i=l; i<=mid; i++) {while(hd<tl && (p[i].y-Queue[tl].y)*(Queue[tl].x-Queue[tl-1].x)<=(Queue[tl].y-Queue[tl-1].y)*(p[i].x-Queue[tl].x))tl--;Queue[++tl]=p[i];}for(re i=mid+1; i<=r; i++) {while(hd<tl && slope(Queue[hd],Queue[hd+1])<=p[i].x*2)	hd++;int x=p[i].id,y=Queue[hd].id;dp[x]=min(dp[x],dp[y]+(h[x]-h[y])*(h[x]-h[y])+sumw[x-1]-sumw[y]);}
//	if(l==1 && r==n) {
//		puts("我永远喜欢珂朵莉");
//	}CDQ_Divide(mid+1,r);Merge(l,r);
}
void Kutori() {n=read();for(re i=1; i<=n; i++) {h[i]=read();p[i].x=h[i];p[i].id=i;}for(re i=1; i<=n; i++) {w[i]=read();sumw[i]=sumw[i-1]+w[i];}memset(dp,0x3f,sizeof(dp));dp[1]=0;sort(p+1,p+1+n,comp);CDQ_Divide(1,n);printf("%lld",dp[n]);
}}
int main() {I_Love::Kutori();return 0;
}