YbtOJ 494「斜率优化 dp」最小划分
题目链接：YbtOJ #494
小 A 有一个长度为 n 的序列 a，要求你把它划分成 m 个连续段（记 w_i 表示 第 i 段的数之和）。
他还给定了一个参数 p，希望你求出 sum_{i=1}^m(w_i p)^2 的最小值。
2le mle nle10^5，1le a_i,ple10^3。
Solution
首先拆平方，得到 sum_{i=1}^m(w_i^2 2cdot w_icdot p p^2)=sum_{i=1}^mw_i^2 (2psum_{i=1}^na_i mp^2)。
后面两项是定值，也就是说只要最小化 sum_{i=1}^mw_i^2。
发现可以 WQS 二分，二分一个额外代价 C，然后每次转移 f 的时候附加上一个 C，并记录 g 表示最优解划分的段数。那么只要找到一个最小的 C 使得 g_n 小于等于 m 就可以了。
先列出暴力的转移方程：（s表示a的前缀和）
把右边的项拆开并且只保留和 j 有关的项得到：
所以一个转移点 j 优于 k（j > k）的充要条件就是
由于 s_j-s_k 显然为正，因此就有：
那么我们只要维护一个单调队列，然后就可以轻松斜率优化了。
Code
代码语言：javascript复制#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc .h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define W while
#define I inline
#define RI register int
#define LL long long
#define Cn const
#define CI Cn int&
using namespace std;
namespace Debug{
Tp I void _debug(Cn char* f,Ty t){cerr<<f<<'='<<t<<endl;}
Ts I void _debug(Cn char* f,Ty x,Ar... y){W(*f!=',') cerr<<*f ;cerr<<'='<<x<<",";_debug(f 1,y...);}
Tp ostream& operator<<(ostream& os,Cn vector<Ty>& V){os<<"[";for(Cn auto& vv:V) os<<vv<<",";os<<"]";return os;}
#define gdb(...) _debug(#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
namespace FastIO{
#define FS 100000
#define tc() (FA==FB&&(FB=(FA=FI) fread(FI,1,FS,stdin),FA==FB)?EOF:*FA )
#define pc(c) (FC==FE&&(clear(),0),*FC =c)
int OT;char oc,FI[FS],FO[FS],OS[FS],*FA=FI,*FB=FI,*FC=FO,*FE=FO FS;
I void clear() {fwrite(FO,1,FC-FO,stdout),FC=FO;}
Tp I void read(Ty& x) {x=0;RI f=1;W(!isdigit(oc=tc())) f=oc^'-'?1:-1;W(x=(x<<3) (x<<1) (oc&15),isdigit(oc=tc()));x*=f;}
Ts I void read(Ty& x,Ar&... y) {read(x),read(y...);}
Tp I void write(Ty x) {x<0&&(pc('-'),x=-x);W(OS[ OT]=x 48,x/=10);W(OT) pc(OS[OT--]);}
Tp I void writeln(Ty x) {x<0&&(pc('-'),x=-x);W(OS[ OT]=x 48,x/=10);W(OT) pc(OS[OT--]);pc('n');}
}using namespace FastIO;
Cn int N=1e5 10;
int n,m,p,a[N],q[N],h,t;
LL s[N],f[N],g[N];
I bool chk(LL C){
auto A=[&](CI x)->LL{return f[x] s[x]*s[x];};
#define S(x,y) (0.5*(A(y)-A(x))/(s[y]-s[x]))
RI i;for(q[h=t=1]=0,i=1;i<=n;i ){
W(h<t&&S(q[h],q[h 1])<s[i]) h;
f[i]=f[q[h]] 1LL*(s[i]-s[q[h]])*(s[i]-s[q[h]]) C,g[i]=g[q[h]] 1;
W(h<t&&S(q[t-1],q[t])>S(q[t],i)) --t;q[ t]=i;
}return g[n]<=m;
}
int main(){
freopen("divide.in","r",stdin),freopen("divide.out","w",stdout);
RI i;for(read(n,m,p),i=1;i<=n;i ) read(a[i]),s[i]=s[i-1] a[i];
LL l=0,r=1e18,mid;W(l<r) chk(mid=l r>>1)?r=mid:l=mid 1;
return chk(l),writeln(f[n] 2*s[n]*p-l*m 1LL*p*p*m),clear(),0;
}
