【CDQ分治】【斜率优化】【DP】CEOI2017 Building

题意：

给出N个柱子，现在要顺次连接它们（从1连到N），每次连接的代价为高度之差的平方。

如果某些柱子不连，那么需要用Wi的代价销毁它。

求最小代价。

神奇的链接（一个叫陈万洲的抄袭狗的博客） ↓ https://www.yunyii.cn/article/Ly9ibG9nLmNzZG4ubmV0L3FxXzM0NDU0MDY5L2FydGljbGUvZGV0YWlscy84MzM4MTk5Mg==

---

分析：

很显然的DP 很显然的斜率优化

推出来一坨东西后，发现需要满足的斜率$(2\times h_i)$不是单调的。

所以。。。CDQ分治啊。。。

先按$h_i$升序排列。

在处理$[l,r]$区间时，先按照编号，分为较小的较大的两部分。（因为只有编号较小的会对编号较大的做出贡献）

然后先处理小的部分，把小的部分的DP值算出来。

然后再通过小的部分来更新大的部分的答案。

然后再处理右半部分。

当然，返回的时候不能忘了把顺序还原为按h值升序

#include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #define SF scanf #define PF printf #define MAXN 100010 using namespace std; typedef long long ll; struct node{ ll x,y,id; }p[MAXN],tmp[MAXN]; int q[MAXN]; ll dp[MAXN],h[MAXN],w[MAXN],pre[MAXN]; int n; bool sort_by_x(const node &a,const node &b){ if(a.x!=b.x) return a.x<b.x; return a.id<b.id; } void CDQ(int l,int r){ // PF("{%d %d}\n",l,r); // for(int i=1;i<=n;i++) // PF("[%lld %lld %lld %lld]\n",p[i].x,p[i].id,p[i].y,dp[p[i].id]); // PF("-------------------\n"); if(l==r){ p[l].y=dp[l]+h[l]*h[l]-pre[l]; return ; } int mid=(l+r)>>1; int xl=l,xr=mid+1; for(int i=l;i<=r;i++){ if(p[i].id<=mid) tmp[xl++]=p[i]; else tmp[xr++]=p[i]; } for(int i=l;i<=r;i++) p[i]=tmp[i]; CDQ(l,mid); int head=1,tail=0; for(int i=l;i<=mid;i++){ while(head<tail&&1.0*(p[i].y-p[q[tail]].y)*(1.0*(p[q[tail]].x-p[q[tail-1]].x))<=1.0*(p[q[tail]].y-p[q[tail-1]].y)*(1.0*(p[i].x-p[q[tail]].x))) tail--; q[++tail]=i; } for(int id=mid+1;id<=r;id++){ int i=p[id].id; while(head<tail&&1.0*(p[q[head+1]].y-p[q[head]].y)<=2.0*h[i]*(1.0*(p[q[head+1]].x-p[q[head]].x))) head++; int j=p[q[head]].id; dp[i]=min(dp[i],dp[j]+(h[i]-h[j])*(h[i]-h[j])+pre[i-1]-pre[j]); } CDQ(mid+1,r); xl=l,xr=mid+1; for(int i=l;i<=r;i++){ if(xr>r||(xl<=mid&&p[xl].x<p[xr].x)) tmp[i]=p[xl++]; else tmp[i]=p[xr++]; } for(int i=l;i<=r;i++) p[i]=tmp[i]; } int main(){ memset(dp,0x3f,sizeof dp); SF("%d",&n); for(int i=1;i<=n;i++) SF("%lld",&h[i]); for(int i=1;i<=n;i++){ SF("%lld",&w[i]); pre[i]=pre[i-1]+w[i]; } for(int i=1;i<=n;i++){ p[i].id=i; p[i].x=h[i]; } sort(p+1,p+1+n,sort_by_x); dp[1]=0; CDQ(1,n); PF("%lld",dp[n]); } /* 6 3 8 7 1 6 6 0 -1 9 1 2 0 */