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

yzxoi

发布于 2022-09-19 13:56:12

7050

发布于 2022-09-19 13:56:12

文章被收录于专栏：OI

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

题目链接：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）的充要条件就是

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

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

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

Code

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

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2022-02-13 ，如有侵权请联系 cloudcommunity@tencent.com 删除