基于 CDQ 分治的决策单调性优化 dp

EnofTaiPeople · 2023-02-10 10:24:23 · 题解

设 dp(x) 表示前 x 人分成若干段的修正战斗力最大值。

有转移方程：dp(x)=\min\limits_{y<x}dp(y)+f(sx_x-sx_y)。

其中 sx_x 表示 \sum\limits_{i=1}^xx_i，在本题中单调递增，f(x)=x^2+bx+c，是一个二次函数。

将函数求导，得 f'(x)=2ax+b，而本题中 a<0，故该函数导函数递减（往不优的方向发展），于是该 dp 方程满足决策单调性。

当然，你也可以认为，设 w(x,y)=f(sx_y-sx_x)，o<p<q<r，则有：

故 w(o,q)+w(p,r)>w(o,r)+w(p,q)，w(x,y) 满足四边形不等式，该转移方程满足决策单调性。

然后就是如何使用了，显然你可以二分队列，但我就是想用实现难度最低的分治怎么办？这道题又要先转移前面的，再转移后面的，发现这是一个前面向后面产生贡献的过程，所以在外面套一个 CDQ 分治就可以了，时间复杂度 O(n\log_2^2n)，但是常数极小（极限数据也是），所以可以通过此题：

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+6;
using ll=long long;
int T,n,A,B,C,sx[N];
ll f[N];
inline ll W(int l,int r){
    ll d=sx[r]-sx[l];
    return d*(d*A+B)+C+f[l];
}
void solve(int l,int r,int L,int R){
    if(l>r||L>R)return;
    int md=L+R>>1,nl=l,i;
    ll now=W(l,md),rp;
    for(i=l+1;i<=r&&i<=md;++i)
        if((rp=W(i,md))>now)now=rp,nl=i;
    f[md]=max(f[md],now);
    if(L<md)solve(l,nl,L,md-1);
    if(md<R)solve(nl,r,md+1,R);
}
void cdq(int l,int r){
    if(l<r){
        int md=l+r>>1;cdq(l,md);
        solve(l,md,md+1,r),cdq(md+1,r);
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>A>>B>>C;int i;
    for(i=1;i<=n;++i)
        cin>>sx[i],sx[i]+=sx[i-1],f[i]=-1e18;
    cdq(0,n),printf("%lld\n",f[n]);
    return 0;
}