YbtOJ 494「斜率优化 dp」最小划分

(Updated: )
oi
, ,

题目链接：YbtOJ #494

小 A 有一个长度为 $n$ 的序列 $a$，要求你把它划分成 $m$ 个连续段（记 $w_i$ 表示 第 $i$ 段的数之和）。

他还给定了一个参数 $p$，希望你求出 $\sum_{i=1}^m(w_i+p)^2$ 的最小值。

$2\le m\le n\le10^5$，$1\le a_i,p\le10^3$。

Solution

首先拆平方，得到 $\sum_{i=1}^m(w_i^2+2\cdot w_i\cdot p+p^2)=\sum_{i=1}^mw_i^2+(2p\sum_{i=1}^na_i+mp^2)$。

后面两项是定值，也就是说只要最小化 $\sum_{i=1}^mw_i^2$。

发现可以 WQS 二分，二分一个额外代价 $C$，然后每次转移 $f$ 的时候附加上一个 $C$，并记录 $g$ 表示最优解划分的段数。那么只要找到一个最小的 $C$ 使得 $g_n$ 小于等于 $m$ 就可以了。

先列出暴力的转移方程：（$s$表示$a$的前缀和）

$$
f_i=f_j+(s_i-s_j)^2+C
$$

把右边的项拆开并且只保留和 $j$ 有关的项得到：

$$
f_j+s_j^2-2s_i\times s_j
$$

所以一个转移点 $j$ 优于 $k$（$j > k$）的充要条件就是：

$$
f_j+s_j^2-2s_i\times s_j < f_k+s_k^2-2s_i\times s_k\
(f_j+s_j^2)-(f_k+s_k^2) < 2s_i\times(s_j-s_k)
$$

由于 $s_j-s_k$ 显然为正，因此就有：

$$
s_i > \frac{(f_j+s_j^2)-(f_k+s_k^2)}{2(s_j-s_k)}
$$

那么我们只要维护一个单调队列，然后就可以轻松斜率优化了。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#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%10+48,x/=10);W(OT) pc(OS[OT--]);}
    Tp I void writeln(Ty x) {x<0&&(pc('-'),x=-x);W(OS[++OT]=x%10+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;
}