题解：P3628 [APIO2010] 特别行动队

· · 题解

看见题解区没有用李超树的，我当然要来水水咕值了。

套路的，我们先写暴力的 dp 式子。

dp_i=\displaystyle \min _{j=0}^{i-1}\{dp_j+a\times (sum_i-sum_j)^2+b \times (sum_i-sum_j)+c\}

然后，让我们把它完全展开以方便优化。

dp_i=dp_j+a\times sum_i^2+a \times sum_j^2-2a\times sum_i\times sum_j+b\times sum_i-b\times sum_j+c

我们发现其中只有一项同时和 i 与 j 相关，很明显的斜率优化。我们把它美化一下。

dp_i=-2a\times sum_j\times sum_i+dp_j+a \times sum_j^2-b\times sum_j+a\times sum_i^2+b\times sum_i+c

这个时候斜率优化的式子就很明显了，令 y=dp_i,k=-2a\times sum_j,x=sum_i,b=a \times sum_j^2-b\times sum_j，那它就是函数取最值的板子，可以使用李超树维护。

还有一点小细节就是李超树不能动态开点，否则会炸空间，需要将 x 的取值离散化之后再插到李超树里面。

下面给出我的实现并不精细的代码。

// Problem: P3628 [APIO2010] 特别行动队
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3628
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// Author: Binah_cyc

#include<bits/stdc++.h>
using namespace std;
#define int long long
constexpr int N=1e6+5;
int n,A,B,C,a[N];
vector<int> b;

struct Segment
{
    int k,b;
    int operator()(int x){return k*::b[x]+b;}
    Segment(int _k=0,int _b=INT_MIN){k=_k,b=_b;}
}t[N<<2];
void change(Segment id,int tl=1,int tr=n,int p=1)
{
    int mid=(tl+tr)>>1;
    if(t[p](mid)<id(mid)) swap(t[p],id);
    if(t[p](tl) <id(tl) ) change(id,tl,mid,p<<1);
    if(t[p](tr) <id(tr) ) change(id,mid+1,tr,p<<1|1);
}
int ask(int x,int tl=1,int tr=n,int p=1)
{
    if(tl==tr) return t[p](x);
    int mid=(tl+tr)>>1;
    if(x<=mid) return max(t[p](x),ask(x,tl,mid,p<<1));
    else return max(t[p](x),ask(x,mid+1,tr,p<<1|1));
}
//以上是李超树板子,我实现的可能有点丑

int dp[N];

main()
{
    cin.tie(0)->sync_with_stdio(false);
    cin>>n>>A>>B>>C;
    for(int i=1;i<=n;i++) cin>>a[i],a[i]+=a[i-1];
    b.push_back(-1);
    for(int i=1;i<=n;i++) b.push_back(a[i]);
    sort(b.begin(),b.end()),b.erase(unique(b.begin(),b.end()),b.end());
    change({0,0});//它代表dp[0]
    for(int i=1;i<=n;i++)
    {
        dp[i]=ask(lower_bound(b.begin(),b.end(),a[i])-b.begin())+A*a[i]*a[i]+B*a[i]+C;//转移
        change({-2*A*a[i],dp[i]+A*a[i]*a[i]-B*a[i]});//插线段
    }
    cout<<dp[n];
    return 0;
}