[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;
}