斜率单调暴力移指针
斜率不单调二分找答案
\(x\) 坐标单调开单调队列
\(x\) 坐标不单调开平衡树 / cdq分治
P4072 [SDOI2016]征途
我们要求方差最小，而总和不变，等价于要每天走的路程平方和最小。
设 \(s(i)\) 表示前 \(i\) 段路的距离总和。
首先我们有一个 naive 的 \(O(n^3)\) DP：
设 \(f(i,j)\) 表示走完前 \(n\) 段，用了 \(j\) 天的最小平方和。
\[f(i,j)=\min_{k=0}^i f(k,j-1)+(s(i)-s(k))^2 \]发现后面的 \((s(i)-s(k))^2\) 明显就是斜率优化 DP，我们转化一下形式：
\[\begin{aligned} f_j(i)&=\min_{k=0}^i f_{j-1}(k)+s^2(i)+s^2(k)-2s(i)s(k) \\&=s^2(i)+\min_{k=0}^i f_{j-1}(k)+s^2(k)-2s(i)s(k) \end{aligned} \]若转移至 \(f_j(i)\) 时 \(k_0\) 不比 \(k\) 劣，则有
\[f_{j-1}(k_0)+s(k_0)^2-2s(i)s(k_0)\le f_{j-1}(k)+s^2(k)-2s(i)s(k) \]将 \(i\) 有关移到一侧:
\[\frac{(f_{j-1}(k_0)+s(k_0)^2)-(f_{j-1}(k)+s^2(k))}{s(k_0)-s(k)}\le 2s(i) \]不妨设 \(g(k)=f_{j-1}(k)+s^2(k)\)，则
\[\frac{g(k_0)-g(k)}{s(k_0)-s(k)}\le 2s(i) \]发现左边就是 \((s(k_0),g(k_0)),(s(k),g(k))\) 两点间的斜率。
所以说，我们对于每一次 \(j-1\to j\)，都进行斜率优化，复杂度 \(O(n^2)\)。
（\(x\) 坐标单调开单调队列）
点击查看代码
//We'll be counting stars.
//#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
#define fir first
#define sec second
#define mkp make_pair
#define pb emplace_back
#define For(i,j,k) for(int i=(j),i##_=(k);i<=i##_;i++)
#define Rof(i,j,k) for(int i=(j),i##_=(k);i>=i##_;i--)
#define ckmx(a,b) a=max(a,b)
#define ckmn(a,b) a=min(a,b)
#define debug(...) cerr<<"#"<<__LINE__<<": "<<__VA_ARGS__<<endl
#define int long long
#define db double
#define N 3003
int n,m,a[N],f[2][N],q[N],head,tail;
inline int pw(int x){ return x*x; }
db SL(bool o,int x,int y){//slope
return 1.*((f[o][y]+pw(a[y]))-(f[o][x]+pw(a[x])))/(a[y]-a[x]);
}
signed main(){ios::sync_with_stdio(false),cin.tie(nullptr);
cin>>n>>m;
For(i,1,n) cin>>a[i];
For(i,2,n) a[i]+=a[i-1];
For(i,1,n) f[1][i]=pw(a[i]);
bool o;
int tmp;
For(i,2,m){
o=(i&1)^1;
head=1,tail=0;
For(j,1,n){
while(head<tail && SL(o,q[head],q[head+1])<2*a[j])
head++;
tmp=q[head];
f[o^1][j]=f[o][tmp]+pw(a[j]-a[tmp]);
while(head<tail && SL(o,q[tail-1],q[tail])>=SL(o,q[tail],j))
tail--;
q[++tail]=j;
}
}
tmp=f[m&1][n];
cout<<m*tmp-pw(a[n]);
return 0;}