[CEOI2017] Building Bridges 题解

[CEOI2017] Building Bridges

什么？你不知道李超线段树

1.题目大意

有$n$根柱子，每根柱子有个高度$h_i$，有若干座桥，一座连接柱子$i$和$j$的桥建造它需要$(h_i-h_j)^2$的代价。

要求连接$1$到$n$的所有柱子。但是用不到的柱子全要被拆除，拆除第$i$根柱子的代价为$w_i$。

2.DP设计与优化思路

十分简单

为了方便表示，设$s_i=\sum_{j=1}^{i}w_j$

设$dp_i$为将第一根柱子通过不同的连接方案连接上第$i$根柱子的最小代价，这个状态很好转移，就像这样：

$$
dp_i=\min\limits_{j=1}^{i-1} {dp_j+(h_i-h_j)^2+s_i-s_{j}}
$$

这个转移是$O(n^2)$的，此时，我们想起之前学过斜率优化DP，发现这个式子似乎可以拆成如下的形式：

$$
dp_i=\min\limits_{j=1}^{i-1} {dp_j+h_j^2-s_j-2h_ih_j}+h_i^2+s_i
$$

观察$min$内的柿子，这个式子可以变为如$kx+b$的形式

设$k=-2h_j$，$b=dp_j+h_j^2-s_j$，再把$min$括号内的$h_i$看作$x$

那就化成了如下的形式：

$$
dp_i=\min\limits_{j=1}^{i-1} {kh_i+b}+h_i^2+s_i
$$

问题就转化为了：有$i-1$条直线，求所有 直线中与$x=h_i$这条直线相交的点$y$坐标最低 的直线

这道题的DP没有单调性，但是我们有数据结构：李超线段树

于是，每次按照$k=-2h_j$，$b=dp_j+h_j^2-s_j$插入每条线段，查询最低点就行了。

思路还是比较套路的，可以用到许多其他类似的DP上

3.警示后人

如果你把所有区间的优势线段初始化为$0$，请设置第$0$个线段的值为极大值

4.Code

#include<bits/stdc++.h>
#define int long long
#define ls (k<<1)
#define rs (k<<1|1)
using namespace std;
const int mod1=39989,mod2=1e9;
struct no{
	int k,b;
}ln[2000010];
int rt[2000010],cnt;
int gsum(int id,int val){
	return ln[id].k*val+ln[id].b;
}
void add(int k,int b){
	ln[++cnt]={k,b};
}
int cmp(int a,int b){
	if(a-b>0)return 1;
	if(b-a>0)return -1;
	return 0;
}
void change(int k,int l,int r,int pos){
	int &tmp=rt[k],mid(l+r>>1);
	int op2=cmp(gsum(pos,mid),gsum(tmp,mid));
	if(op2==-1 or (op2==0 and pos<tmp))swap(tmp,pos);
	int op1=cmp(gsum(pos,l),gsum(tmp,l));
	int op3=cmp(gsum(pos,r),gsum(tmp,r));
	if(op1==-1 or (op1==0 and pos<tmp))change(ls,l,mid,pos);
	if(op3==-1 or (op3==0 and pos<tmp))change(rs,mid+1,r,pos);
}

pair<int,int> mxp(pair<int,int>a,pair<int,int>b){
	if(cmp(a.first,b.first)==1)return b;
	if(cmp(a.first,b.first)==-1)return a;
	return a.second<b.second ? a:b;
}
pair<int,int>query(int k,int l,int r,int val){

	if(r<val or val<l)return {1e18,1e18};
	int mid(l+r>>1);
	//cout<<l<<" "<<r<<" "<<val<<endl;
	int now=gsum(rt[k],val);
	if(l==r)return {now,rt[k]};
	return mxp({now,rt[k]},mxp(query(ls,l,mid,val),query(rs,mid+1,r,val)));
}
int n,h[200010],w[200010],f[200010];
main(){
	cin>>n;
	for(int i=1;i<=n;i++)cin>>h[i];
	for(int i=1;i<=n;i++)cin>>w[i],w[i]+=w[i-1];
	ln[0].b=1e18;
	add(-2*h[1],h[1]*h[1]-w[1]);
	change(1,0,1000000,cnt);
	//cout<<1;
	for(int i=2;i<=n;i++){

		f[i]=h[i]*h[i]+w[i-1]+query(1,0,1000000,h[i]).first;//cout<<i<<endl;
		add(-2*h[i],f[i]+h[i]*h[i]-w[i]);
		change(1,0,1000000,cnt);
	}
	cout<<f[n];
	return 0;
}