斜率优化
- 斜率优化，一般是在转移方程中当前为 $i$，枚举决策点 $j$，然后化简式子出现同时与 $i$ 和 $j$ 有关的项（如果没有可以单调队列）。这样的话有点像一次函数，形如 $y=kx+b$，那么这里的 $kx$ 就是与$i$ 和 $j$ 有关的项（具体题目具体分析）。问题变成查询最有决策点。
- 如果式子中的 $x$ 与 $y$ 都有单调性，可以使用单调队列线性维护。否则有两种做法：维护凸壳并二分或李超树（也可以平衡树或 cdq 分治，但我不会，就不弄巧成拙了）。这些做法是带一个 log 的。
经典套路：
$1.$ 写出朴素转移方程。
$2.$ 化简并设出 $x,y,k,b$，根据所求决定维护上凸还是下凸（最大值还是最小值）。
$3.$ 看单调性决定维护方式。
单调队列维护
【题意】
给定一个序列，要求将其划分成若干段，一段划分为 $[i,j]$ 的费用为 $(j-i+\sum_{k=i}^jC_k-L)^2$（这里的 $C_k$ 为给定数组，$L$ 为给定常量）。最小化划分序列的费用和。
【解析】
朴素的转移方程为：（设 $f_i$ 表示考虑到 $i$ 的答案，$s_i$ 表示 $C_i$ 的前缀和）
$$
f_i=\min_{1\le j<i}(f_j+[i-(j+1)+s_i-s_j-L]^2)
$$
换元并化简，设 $a_i=s_i+i，b_i=s_i+i+L+1$。
$$
\begin{aligned}
&f_i=\min_{1\le j<i}(f_j+[a_i-b_j]^2)\\
&f_i=\min_{1\le j<i}(f_j+a_i^2+b_j^2-2\times a_i\times b_j)
\end{aligned}
$$
先不管取 $\min$，先推式子，并把只与 $j$ 有关的移到一边，尝试分离 $i$ 和 $j$。
$$
\begin{aligned}
f_i&=f_j+a_i^2+b_j^2-2\times a_i\times b_j\\
f_j+b_j^2&=f_i-a_i^2+2\times a_i\times b_j
\end{aligned}
$$
我们发现，如果设 $y=f_j+b_j^2，k=2\times a_i，x=b_j，b=f_i-a_i^2$，那么方程变成了一个一次函数形式 $y=kx+b$。所以要做的就是在二维平面中找一个斜率固定的直线使 $b$ 最小。
观察数据，$y=f_j+b_j^2$ 和 $x=b_j$ 都单调递增，所以使用单调队列优化，时空复杂度线性。
放个单调队列斜优的板子吧。
代码中没用 $\text{double}$，防止爆精度。
#include<iostream>
using namespace std;
#define int long long
#define endl '\n'
#define N 100005
int n,l;
int s[N],f[N],q[N];
int up(int i,int j){
return (f[j]+s[j]*s[j]+2*l*s[j])-(f[i]+s[i]*s[i]+2*l*s[i]);
}
int down(int i,int j){
return s[j]-s[i];
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin>>n>>l;
l=l+1;
for(int i=1,x;i<=n;++i) cin>>x,s[i]=s[i-1]+x;
for(int i=1;i<=n;++i) s[i]=s[i]+i;
int h=1,t=1;
q[1]=0;
for(int i=1;i<=n;++i){
int k=2*s[i];
while(h<t&&up(q[h],q[h+1])<=down(q[h],q[h+1])*k) h++;
int j=q[h];
f[i]=f[j]+(s[i]-s[j]-l)*(s[i]-s[j]-l);
while(h<t&&up(q[t-1],q[t])*down(q[t],i)>=up(q[t],i)*down(q[t-1],q[t])) t--;
q[++t]=i;
}
cout<<f[n]<<endl;
return 0;
}
|
与此题类似的题：
P3628 [APIO2010] 特别行动队
P2365 任务安排
P4360 [CEOI2004] 锯木厂选址
【题意】
给定长度为 $n$ 的序列，将其划分为 $m$ 段，使得这 $m$ 段各自求和后的总方差最小，输出方差 $\times m^2$。
形式化地，设 $b_i=\sum_{j=l_i}^{r_i}a_j$，$v=\frac{\sum_{i=1}^m(b_i-\bar{b})^2}{m}$，求最小的 $v\times m^2$。其中 $\forall i\in [1,m-1]$，$l_{i+1}=r_i+1$。
【解析】
推推柿子。
$$
\begin{aligned}
v&=\frac{\sum_{i=1}^m(b_i-\bar{b})^2}{m}\\
&=\frac{(b_1-\bar{b})^2+ (b_2-\bar{b})^2+…+ (b_m-\bar{b})^2}{m}\\
&=\frac{m\times(\bar{b})^2+\sum_{i=1}^mb_i^2-2\times \bar{b}\times\sum_{i=1}^mb_i}{m}\\
&=\frac{m\times(\frac{\sum_{i=1}^mb_i}{m})^2+\sum_{i=1}^mb_i^2-2\times \frac{\sum_{i=1}^mb_i}{m}\times\sum_{i=1}^mb_i}{m}\\
&=\frac{\frac{(\sum_{i=1}^mb_i)}{m}^2+\sum_{i=1}^mb_i^2-2\times \frac{(\sum_{i=1}^mb_i)^2}{m}}{m}\\
&=\frac{\sum_{i=1}^mb_i^2- \frac{(\sum_{i=1}^mb_i)^2}{m}}{m}\\
v\times m^2&=m\times\sum_{i=1}^mb_i^2-(\sum_{i=1}^mb_i)^2
\end{aligned}
$$
可以发现， $-(\sum_{i=1}^mb_i)^2$ 无论怎么划分都不会变，都是 $-(\sum_{i=1}^na_i)^2$，所以就变成最小化 $m\times\sum_{i=1}^mb_i^2$。
考虑 DP 设 $f_{i,j}$ 表示走到 $a_i$，是第 $j$ 天的最小 $\sum_{}$（最后再乘 $m$）。那么朴素式子很好推（这里的 $s_i$ 表示 $a_i$ 的前缀和）：
$$
f_{i,j}=\min_{1\le k<i}(f_{k,j-1}+(s_i-s_k)^2)
$$
直接做是 $O(n^3)$ 的，发现这是斜率优化的经典形式，即
$$
\begin{aligned}
f_{i,j}&=\min_{1\le k<i}(f_{k,j-1}+s_i^2+s_k^2-2\times s_i\times s_k)\\
f_{i,j}&=f_{k,j-1}+s_i^2+s_k^2-2\times s_i\times s_k\\
f_{k,j-1}+s_k^2&=f_{i,j}-s_i^2+2\times s_i\times s_k
\end{aligned}
$$
设 $y=f_{k,j-1}+s_k^2,k=2\times s_i,x=s_k,b=f_{i,j}-s_i^2$，变成一次函数形式，即可斜率优化。此题斜率优化是二维的，使用了单调队列。
放个二维斜率优化的板子。使用了辅助数组 $g$，优化成线性空间。
#include<iostream>
using namespace std;
#define int long long
#define N 3005
int n,m;
int s[N],q[N],f[N],g[N];
int up(int i,int j){
return (g[j]+s[j]*s[j])-(g[i]+s[i]*s[i]);
}
int down(int i,int j){
return s[j]-s[i];
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin>>n>>m;
for(int i=1,x;i<=n;++i) cin>>x,s[i]=s[i-1]+x,g[i]=s[i]*s[i];
for(int j=2;j<=m;++j){
int h=1,t=1;
q[1]=j-1;
for(int i=j;i<=n;++i){
while(h<t&&up(q[h],q[h+1])<=down(q[h],q[h+1])*2*s[i]) h++;
int p=q[h];
f[i]=g[p]+(s[i]-s[p])*(s[i]-s[p]);
while(h<t&&up(q[t-1],q[t])*down(q[t],i)>=up(q[t],i)*down(q[t-1],q[t])) t--;
q[++t]=i;
}
for(int i=1;i<=n;++i) g[i]=f[i];
}
cout<<m*f[n]-s[n]*s[n]<<endl;
return 0;
}
|
与此题类似的题：
P3648 [APIO2014] 序列分割
李超线段树维护
李超线段树，用来维护直线或线段上的信息。简单来说就是个标记永久化的线段树。
例如，我们要维护一些直线，查询横坐标为 $x$ 时纵坐标的最大值。
先考虑维护修改，第一步判断中点信息，选那个更大的作为主要线段（这样保证不会更劣），第二步分别比较两端点，确定一下哪边更大，然后递归处理。
具体地，设 $g$ 为主要线段，$f$ 为修改线段，默认 $f_{mid}<g_{mid}$。若 $f_l>g_l$，说明左半边有交点，递归左二子，右边同理。若 $f_l<g_l,f_r<g_r$，则无需递归，$g$ 完全优于 $f$。
查询的话，就是标记永久化以后一路查询最值。
放个李超树板子
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define db double
const int N=1e5+10;
const double eps=1e-8;
db Abs(db x){return (x<0)?-x:x;}
struct line{
db k,b;
int id;
line(){k=0,b=-1e18;}
line(db h1,db z1,db h2,db z2,int _id){
id=_id;
if(Abs(h1-h2)<eps) k=0,b=max(z1,z2);
else{
k=(z2-z1)/(h2-h1);
b=z2-k*h2;
}
}
db val(db x){return k*x+b;}
}t[N<<3];
void insert(int p,int l,int r,int L,int R,line f){
if(L<=l&&r<=R){
if(t[p].id==0) return t[p]=f,void();
int mid=(l+r)>>1;
if(Abs(t[p].val(mid)-f.val(mid))<eps){
if(t[p].id>f.id) swap(f,t[p]);
}
else if(t[p].val(mid)<f.val(mid)) swap(f,t[p]);
if(f.val(l)+eps>t[p].val(l)) insert(p<<1,l,mid,L,R,f);
if(f.val(r)+eps>t[p].val(r)) insert(p<<1|1,mid+1,r,L,R,f);
return ;
}
int mid=(l+r)>>1;
if(L<=mid) insert(p<<1,l,mid,L,R,f);
if(mid+1<=R) insert(p<<1|1,mid+1,r,L,R,f);
}
line query(int p,int l,int r,int k){
if(l==r) return t[p];
int mid=(l+r)>>1;
line res;
if(k<=mid) res=query(p<<1,l,mid,k);
else res=query(p<<1|1,mid+1,r,k);
if(Abs(res.val(k)-t[p].val(k))<eps){
if(res.id<t[p].id) return res;
return t[p];
}
else{
if(res.val(k)>t[p].val(k)) return res;
return t[p];
}
}
int lans,h1,h2,z1,z2,x,tot;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T,op;
cin>>T;
while(T--){
cin>>op;
if(op==1){
cin>>h1>>z1>>h2>>z2;
h1=(h1+lans-1)%39989+1;
h2=(h2+lans-1)%39989+1;
z1=(z1+lans-1)%1000000000+1;
z2=(z2+lans-1)%1000000000+1;
if(h1>h2) swap(h1,h2),swap(z1,z2);
line c=line(h1,z1,h2,z2,++tot);
insert(1,1,40000,h1,h2,c);
}
else{
cin>>x;
x=(x+lans-1)%39989+1;
lans=query(1,1,40000,x).id;
cout<<lans<<endl;
}
}
return 0;
}
|
【解析】
设 $f_i$ 表示第 $i$ 天最大的收益。
初始条件 $f_0=s$，答案 $f_n$。
转移枚举上一个全买券的点 $j$，设 $y$ 表示第 $j$ 天买 $B$ 的数量，解方程。
$Rate_j\times y_j\times a_j+y_j\times b_j=f_j$
得到 $y_j=\large\frac{f_j}{Rate_j\times a_j+b_j}$
设 $x$ 表示买 $A$ 的数量，显然 $x_i=Rate_j\times y_i$
转移方程 $f_i=\max(f_{i-1},\max{a_i\times x_j+b_i\times y_j | j\in[1,i) } )$
提出 $b_i$，得到 $f_i=\max(f_{i-1},b_i\times \max{\large\frac{a_i}{b_i}\small\times x_j+y_j})$
发现变成一次函数形式，即对于每个 $x_j,y_j$，查询 $\large\frac{a_i}{b_i}$ 处的最大值即可。
李超线段树。
db val(int i,int t){return x[t]*k[i]+y[t];}
void modify(int p,int id,int l,int r){
if(l==r){
if(val(l,id)>val(l,t[p])) t[p]=id;
return;
}
int mid=(l+r)>>1;
if(val(mid,id)>val(mid,t[p])) swap(id,t[p]);
if(val(l,id)>val(l,t[p])) modify(ls,id,l,mid);
else modify(rs,id,mid+1,r);
}
db query(int p,int l,int r){
if(l==r) return val(now,t[p]);
int mid=(l+r)>>1;
if(now<=mid) return Max(val(now,t[p]),query(ls,l,mid));
return Max(val(now,t[p]),query(rs,mid+1,r));
}
int main(){IOS;
int n,s;
cin>>n>>s;
f[0]=s;
F(i,1,n) cin>>a[i]>>b[i]>>r[i],k[i]=a[i]/b[i],kk[i]=k[i];
sort(k+1,k+1+n);
F(i,1,n){
now=lower_bound(k+1,k+n+1,kk[i])-k;
f[i]=max(f[i-1],b[i]*query(1,1,n));
db tmp=a[i]*r[i]+b[i];
y[i]=f[i]/tmp;
x[i]=r[i]*y[i];
modify(1,i,1,n);
}
cout<<fixed<<setprecision(3)<<f[n]<<endl;
return 0;
}
|
与此题类似的题：
P2497 [SDOI2012] 基站建设
P5504 [JSOI2011] 柠檬
P4655 [CEOI2017] Building Bridges
完结撒花！
