浅谈 - 斜率优化dp

· · 算法·理论

点击此处传送至【博客园】食用体验更佳(有动图)

CF1083E The Fair Nut and Rectangles

先把矩形按 x 从小到大排序。

因为没有嵌套的矩形,所以容易得出新加入一个矩形的面积为 y_i\times(x_i-x_j)(如图)。

设 f_i 表示前 i 个矩形,第 i 个矩形必选的最大值。

状态转移方程为:f_i=\max\{f_j+y_i\times(x_i-x_j)-a_i\}。

易得 n^2 DP 暴力:

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+5,INF=0x3f3f3f3f3f3f3f3f;
int n,f[N],ans;
struct node{int x,y,a;}a[N];
bool cmp(node a,node b){return a.x<b.x;}
signed main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i].x>>a[i].y>>a[i].a;
    sort(a+1,a+1+n,cmp);
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<i;j++)
            f[i]=max(f[i],f[j]+a[i].y*(a[i].x-a[j].x)-a[i].a);
        ans=max(ans,f[i]);
    }
    cout<<ans<<'\n';
    return 0;
}

考虑对 dp 进行优化。

因为涉及到取 \max,所以可以先把常量取出来:f_i=\max\{f_j-y_i\times x_j\}+y_i\times x_i-a_i。

再观察一下一次函数标准形式:y=kx+b,变换一下形式:

$f_j \implies y,\ y_i \implies k,\ x_j \implies x

这能说明什么?

对每个 (x_j,f_j) 进行在坐标系上描点,对于新加入的 i,找到经过点 (x_j,f_j)、斜率为 y_i 的一条边,与 y 轴产生的交点(就是斜距 b),即为 f_j-y_i\times x_j 的值。

那怎么找到最大的值?

暴力做法是:对于每个 i,扫一遍之前的每个 j,再比较大小。

但这道题有一个性质:因为不存在嵌套的矩形,所以将 x 从小到大排序之后,y 的顺序自然而然也就从大到小了。

要想斜距最大,这条线必须是所有点连接而成的图形的切线。

而随着斜率变小,当前是切线的这个点的之前所有点一定都会经过这个图形,都不可能是切线。

如图,假设此时红线是切线,当斜率变大时,蓝线一定不会是切线。

当红线越过线段 l 时,此时的切线就转移成了绿线。

所以,切线所属的点一定是单调不减一直往后移动的。

可以维护一个全局 now,表示记录当前的切线是哪个点,如果发现后一个点更优(斜距 b 更大),那么把 now 转移到后面一个点,可以用 vector 来维护。(为什么用 vector,后面会讲)。

以下是具体过程:

while(now+1<(int)q.size() && q[now].f-a[i].y*q[now].x<q[now+1].f-a[i].y*q[now+1].x)
    now++;
f[i]=q[now].f-a[i].y*q[now].x+a[i].x*a[i].y-a[i].a;

但是这样有一个问题,就是可能在当前斜率下,后一个点是不优于这个点的,也就导致永远无法 while 循环下去,怎么办呢?

考虑当如图的形式,AB 的斜率大于 BC,可观察到:任意时刻 A 或 C 总有一个直线的斜距大于 B。

所以,在这样的情况下,B 这个点就可以直接扔掉不管。

也就相当于维护了一个上凸包。

代码实现就是这样:

while(q.size()>=2&&ask(q[q.size()-2],q[q.size()-1],{a[i].x,f[i]}))
    q.pop_back();
q.push_back({a[i].x,f[i]});

那如果此时的 now 是 B 点怎么办?如果扔掉不管,之后再调用 q_{now} 不就越界了吗?

有一个很好的处理方法,就是在后面加上 now=min(now,(int)q.size()-1) 这句话。

它的作用是:还看上图,当 now 在 C 点时,不变;但当 now 在删过的数之中时,\min 会把 now 变成最后一个点的位置。

因为只有当直线斜率大于 AB 时,放到 B 的贡献才会大于 A。但是 now 从 C 转移到 B 当且仅当斜率小于 BC。所以此时放到 B 是永远不优于 A 的。

最后,要选取一个支持结尾加入、结尾删除、下标查询的数据结构,非 vector 莫属。

于是代码就写完了。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e6+5,INF=0x3f3f3f3f3f3f3f3f;
int n,f[N],ans;
struct node{int x,y,a;}a[N];
bool cmp(node a,node b){return a.x<b.x;}
struct fog{int x,f;};
vector<fog>q;
bool ask(fog a,fog b,fog c)
{
    return 1.0*(c.f-b.f)/(c.x-b.x) >= 1.0*(b.f-a.f)/(b.x-a.x);
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i].x>>a[i].y>>a[i].a;
    sort(a+1,a+1+n,cmp);
    int now=0;
    q.push_back({0,0});
    for(int i=1;i<=n;i++)
    {
        while(now+1<(int)q.size() && q[now].f-a[i].y*q[now].x<q[now+1].f-a[i].y*q[now+1].x)
            now++;
        f[i]=q[now].f-a[i].y*q[now].x+a[i].x*a[i].y-a[i].a;
        while(q.size()>=2&&ask(q[q.size()-2],q[q.size()-1],{a[i].x,f[i]}))
            q.pop_back();
        q.push_back({a[i].x,f[i]});
        now=min(now,(int)q.size()-1);
        ans=max(ans,f[i]);
    }
    cout<<ans<<'\n';
    return 0;
}

CF311B Cats Transport

仿照上题,一样的套路,先写个 n^2 DP 出来。

拿样例举例,注意到:在第 2 座山第 1 秒出现等价于在第 1 座山第 0 秒出现,第 4 座山第 9 秒出现等价于在第 1 座山第 0 秒出现,在第 2 座山第 10 秒出现等价于在第 1 座山第 9 秒出现。 改变 $d_i$ 的含义:表示第 $i$ 座山距离第 1 座山的距离。相当于做一个前缀和了。$d_i=d_{i-1}+d_i$。 再改变 $t_i$ 的含义:表示第 $i$ 只猫在第 1 座山出现的时间。$d_i-t_i$ 即可。 于是可以将题目转化为:第 $i$ 只猫会在 $t_i$ 秒出现在第 1 座山,你总共可以派 $p$ 次饲养员,每次饲养员会把以前出现的猫都带走,求出所有猫等待的最小时间。 易得转移方程为:$dp_{i,j}=\min\{dp_{k,j-1}+t_i\times(i-k)-(sum_i-sum_k)\}

为了使 i 是当前饲养员带走前最后一个出现的,要把 t_i 按从小到大排序。

代码如下: ```cpp #include<bits/stdc++.h> #define int long long using namespace std; const int N=2e5+5,INF=0x3f3f3f3f3f3f3f3f; int n,m,p,d[N],t[N],sum[N]; int dp[N][105]; signed main() { ios::sync_with_stdio(false); cin.tie(0);cout.tie(0); cin>>n>>m>>p; for(int i=2;i<=n;i++) { int x;cin>>x; d[i]=d[i-1]+x; } for(int i=1;i<=m;i++) { int x;cin>>x; cin>>t[i];t[i]-=d[x]; } sort(t+1,t+1+m); for(int i=1;i<=m;i++) sum[i]=sum[i-1]+t[i]; memset(dp,0x3f,sizeof(dp)); dp[0][0]=0; for(int i=1;i<=m;i++) for(int j=1;j<=p;j++) for(int k=0;k<i;k++)//k+1~i为一个饲养员 dp[i][j]=min(dp[i][j],dp[k][j-1]+t[i]*(i-k)-(sum[i]-sum[k])); cout<<dp[m][p]<<'\n'; return 0; } ``` 优化的话,还是仿照上一题,把 $\min$ 拆开。 $$ \begin{aligned} dp_{i,j}&=\min\{dp_{k,j-1}+t_i\times(i-k)-(sum_i-sum_k)\}\\ &=\min\{dp_{k,j-1}+t_i\times i-t_i\times k-sum_i+sum_k\}\\ &=\min\{dp_{k,j-1}+sum_k-t_i\times k\}+t_i\times i-sum_i\\ \end{aligned} $$ 又看到 $b=y-kx$ 的形式了。 $dp_{k,j-1}+sum_k \implies y,\ t_i \implies k,\ k \implies x

看到这里,是不是想直接搬第一题模版了?但是有两点需要注意。

  1. 本题 dp 为二维。

发现 j-1 是不变的,那就相当于在 [1,i] 的 j-1 层这个集合里找最小值,那就开 p 个 vector 就够了,代表第二维下标为 j 的全体集合。

  1. 本题是取 \min,并且 k 是逐渐递增

先回归斜率优化的本质,在凸包上找一切点,使得斜距最大/小。

取 \max 且 k 递减的情况下,可以沿着上凸包跑。

那取 \min 且 k 递增,就是沿着下凸包跑了。

(删点和单调性具体证明过程与前面类似,这里不再赘述。)

那么代码就非常好写了:

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+5,INF=0x3f3f3f3f3f3f3f3f;
int n,m,p,d[N],t[N],sum[N];
int dp[N][105];//dp[i][j]表示前i只🐱🙀😸😹🐈,用了j个饲养员的最小值。
struct node{int x,f;};
vector<node>q[105];
int now[105];
int ask(node a,node b,node c)
{
    return 1.0*(c.f-b.f)/(c.x-b.x) <= 1.0*(b.f-a.f)/(b.x-a.x);//注意这里是下凸包,<=就删
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>m>>p;
    for(int i=2;i<=n;i++)
    {
        int x;cin>>x;
        d[i]=d[i-1]+x;
    }
    for(int i=1;i<=m;i++)
    {
        int x;cin>>x;
        cin>>t[i];t[i]-=d[x];
    }
    sort(t+1,t+1+m);
    for(int i=1;i<=m;i++)
        sum[i]=sum[i-1]+t[i];
    memset(dp,0x3f,sizeof(dp));
    dp[0][0]=0;
    q[0].push_back({0,0});
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=p;j++)
        {
            while(now[j-1]+1<(int)q[j-1].size()&&
q[j-1][now[j-1]].f-t[i]*q[j-1][now[j-1]].x>q[j-1][now[j-1]+1].f-t[i]*q[j-1][now[j-1]+1].x)
                now[j-1]++;
            dp[i][j]=q[j-1][now[j-1]].f-t[i]*q[j-1][now[j-1]].x+t[i]*i-sum[i];
            while(q[j].size()>=2&&ask(q[j][q[j].size()-2],q[j][q[j].size()-1],{i,dp[i][j]+sum[i]}))
                q[j].pop_back();
            q[j].push_back({i,dp[i][j]+sum[i]});
            now[j]=min(now[j],(int)q[j].size()-1);//好像不加这一行也能过,暂时不知道为什么
        }
    }
    cout<<dp[m][p]<<'\n';
    return 0;
}

任务安排

part 1/2:[IOI 2002] 任务安排

part 3:任务安排 2

part 4:[SDOI2012] 任务安排

part 1

那么,本批任务的完成时间就是 $s\times j+sumt_i$。 枚举 $k$ 作为第 $j-1$ 批和第 $j$ 批的分界点,易得:$dp_{i,j}=\min\{dp_{k,j-1}+(s\times j+sumt_i)\times(sumc_i-sumc_k)\}$。 ```cpp for(int i=1;i<=n;i++) { cin>>t[i]>>c[i]; sumt[i]=sumt[i-1]+t[i]; sumc[i]=sumc[i-1]+c[i]; } memset(dp,0x3f,sizeof(dp)); dp[0][0]=0; for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { for(int k=0;k<i;k++) dp[i][j]=min(dp[i][j],dp[k][j-1]+(s*j+sumt[i])*(sumc[i]-sumc[k])); if(i==n) ans=min(ans,dp[i][j]); } } cout<<ans<<'\n'; ``` **时间复杂度:$O(n^3)$。** ## part 2 思路:费用提前计算。 答案并不要求分多少批次,而我们枚举 $j$ 只是为了求这一批多增加的时间。 但是,我们不容易知道之前有多少批,**但是知道此次启动增加的时间,会导致之后每一个物品的花费都增加 $c_i\times s$。** 根据这个思路,把 $j$ 的枚举省略掉。 $dp_i$ 表示前 $i$ 个任务,分成若干批的最小花费。 $dp_i=\min\{dp_j+sumt_i\times(sumc_i-sumc_j)+s\times(sumc_n-sumc_j)\}$。 对比 part 1 中的 $(s\times j+sumt_i)\times(sumc_i-sumc_k)$,不用 $s\times j\times(sumc_i-sumc_k)$ 是因为之前启动机器造成的影响已经在之前计算过了。 这就是费用提前计算的神力。 代码如下: ```cpp cin>>n>>s; for(int i=1;i<=n;i++) { cin>>t[i]>>c[i]; sumt[i]=sumt[i-1]+t[i]; sumc[i]=sumc[i-1]+c[i]; } memset(dp,0x3f,sizeof(dp)); dp[0]=0; for(int i=1;i<=n;i++) for(int j=0;j<i;j++) dp[i]=min(dp[i],dp[j]+sumt[i]*(sumc[i]-sumc[j])+s*(sumc[n]-sumc[j])); cout<<dp[n]<<'\n'; ``` **时间复杂度:$O(n^2)$。** ## part 3 推公式走起: $$ \begin{aligned} dp_i&=\min\{dp_j+sumt_i\times(sumc_i-sumc_j)+s\times(sumc_n-sumc_j)\}\\ &=\min\{dp_j+sumt_i\times sumc_i-sumt_i\times sumc_j+s\times sumc_n-s\times sumc_j\}\\ &=\min\{dp_j-sumt_i\times sumc_j-s\times sumc_j\}+sumt_i\times sumc_i+s\times sumc_n\\ &=\min\{dp_j-(sumt_i+s)\times sumc_j\}+sumt_i\times sumc_i+s\times sumc_n \end{aligned} $$ 代入: $dp_j \implies y,\ (sumt_i+s) \implies k,\ sumc_j \implies x

答案取 \min,sumt_i+s 大于 0 且单调递增,维护下凸包即可。

代码如下:

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=3e5+5,INF=0x3f3f3f3f3f3f3f3f;
int n,s,t[N],c[N],sumt[N],sumc[N],ans=INF;
int dp[N];//dp[i][j]表示前i个任务,分成若干批的最小花费。
struct node{int x,f;}a[N];
vector<node>q;
int ask(node a,node b,node c)
{
    return 1.0*(c.f-b.f)/(c.x-b.x) <= 1.0*(b.f-a.f)/(b.x-a.x);
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>s;
    for(int i=1;i<=n;i++)
    {
        cin>>t[i]>>c[i];
        sumt[i]=sumt[i-1]+t[i];
        sumc[i]=sumc[i-1]+c[i];
    }
    memset(dp,0x3f,sizeof(dp));
    dp[0]=0;
    int now=0;
    q.push_back({0,0});
    for(int i=1;i<=n;i++)
    {//dp[j]=>y , (sumt[i]+s)=>k , sumc[j]=>x
        while(now+1<(int)q.size()&&
    q[now].f-(sumt[i]+s)*q[now].x>=q[now+1].f-(sumt[i]+s)*q[now+1].x)
            now++;
        dp[i]=q[now].f-(sumt[i]+s)*q[now].x+sumt[i]*sumc[i]+s*sumc[n];
        while(q.size()>=2&&ask(q[q.size()-2],q[q.size()-1],{sumc[i],dp[i]}))
            q.pop_back();
        q.push_back({sumc[i],dp[i]});
        now=min(now,(int)q.size()-1);
    }
    cout<<dp[n]<<'\n';
    return 0;
}

时间复杂度:O(n)。

part 4

与 part 3 不同的是,T_i 可以是负数。

这说明 sumt_i+s(也就是 k)不具有单调性,那么 now 在凸包上跑的前提就失效了。

回想一下,在保证单调性的情况下,我们只需要维护 k 大于 sumt_i+s 的部分。

但是现在单调性消失了,我们就必须维护整个凸壳,now 这个东西直接扔掉不要就行了。

还是之前那句话,要找到一条线,使得斜率等于 k,且为凸壳的切线。此时的斜距就为最小值。

怎么找切线?

发现在这个凸壳里,越靠近切线经过的点,斜距越小,反之就越大。

先钦定选择一个点。如果它左边的点所在直线的斜距大于这个点,那就说明切点一定在这个点的右边,否则就在左边。

这不就是裸的二分吗!

根据刚才的思路,把找 now 的部分换成二分,写一下代码:(注意有精度问题,不能用除法,要用乘法 + int128)。

#include<bits/stdc++.h>
#define int long long
#define pr pair<int,int>
using namespace std;
const int N=3e5+5,INF=0x3f3f3f3f3f3f3f3f;
int n,s,t[N],c[N],sumt[N],sumc[N],ans=INF;
int dp[N];//dp[i]表示前i个任务,分成若干批的最小花费。
struct node{int x,f;}a[N];
vector<node>q;
int ask(node a,node b,node c)
{
    return (__int128)(c.f-b.f)*(b.x-a.x) <= (__int128)(b.f-a.f)*(c.x-b.x);
}
int query(int k)
{
    int l=0,r=q.size()-1;
    while(l+1<r)
    {
        int mid=(l+r)>>1;
        node a=q[mid],b=q[mid+1];
        if(a.f-(__int128)a.x*k>b.f-(__int128)b.x*k) l=mid;
        else r=mid;
    }
    node a=q[l],b=q[r];
    if(a.f-(__int128)a.x*k<b.f-(__int128)b.x*k) return l;
    else return r;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>s;
    for(int i=1;i<=n;i++)
    {
        cin>>t[i]>>c[i];
        sumt[i]=sumt[i-1]+t[i];
        sumc[i]=sumc[i-1]+c[i];
    }
    memset(dp,0x3f,sizeof(dp));
    dp[0]=0;
    q.push_back({0,0});
    for(int i=1;i<=n;i++)
    {//dp[j]=>y , (sumt[i]+s)=>k , sumc[j]=>x
        int now=query(sumt[i]+s);
        dp[i]=q[now].f-(sumt[i]+s)*q[now].x+sumt[i]*sumc[i]+s*sumc[n];
        while(q.size()>=2&&ask(q[q.size()-2],q[q.size()-1],{sumc[i],dp[i]}))
            q.pop_back();
        q.push_back({sumc[i],dp[i]});
        now=min(now,(int)q.size()-1);
    }
    cout<<dp[n]<<'\n';
    return 0;
}

时间复杂度:O(n\log n)。

CF319C Kalila and Dimna in the Logging Industry

设 f_i 表示砍倒 i 所需的最小花费。

如果砍倒了第 n 棵树,那么其他剩下的数都可以免费砍完,所以答案就是 f_n。

易得状态转移方程为:f_i=\min\{f_j+b_j\times a_i\}。

代码:

cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++) cin>>b[i];
memset(f,0x3f,sizeof(f));
f[1]=0;
for(int i=2;i<=n;i++)
    for(int j=1;j<i;j++)
        f[i]=min(f[i],f[j]+b[j]*a[i]);
cout<<f[n]<<'\n';

优化成 O(n),易得 y\implies f_j,\ k\implies a_i,\ x\implies -b_j。

因为取 \min,所以要维护下凸包。但是要求 a_i 必须是单调不减的,所以这个符号不能加到 a_i 上,就只能是 -b_j 了。

然后就是模版。

代码:

#include<bits/stdc++.h>
#define int long long
#define pr pair<int,int>
using namespace std;
const int N=2e5+5,INF=0x3f3f3f3f3f3f3f3f;
int n,a[N],b[N];
int f[N];//f[i]表示砍倒第i棵树的最小总成本。
struct node{int x,f;};
vector<node>q;
bool ask(node a,node b,node c)
{
    return (__int128)(b.f-a.f)*(c.x-b.x) >= (__int128)(c.f-b.f)*(b.x-a.x);
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) cin>>b[i];
    memset(f,0x3f,sizeof(f));
    f[1]=0;
    int now=0;
    q.push_back({-b[1],f[1]});
    for(int i=2;i<=n;i++)
    {//y=>f[j] , k=>a[i] , x=>-b[j]。
        while(now+1<(int)q.size()&&
q[now].f-a[i]*q[now].x>=q[now+1].f-a[i]*q[now+1].x)
            now++;
        f[i]=q[now].f-q[now].x*a[i];
        while(q.size()>=2&&ask(q[q.size()-2],q[q.size()-1],{-b[i],f[i]}))
            q.pop_back();
        q.push_back({-b[i],f[i]});
        now=min(now,(int)q.size()-1);
    }
    cout<<f[n]<<'\n';
    return 0;
}

CF660F Bear and Bowling 4

先写一个 O(n^3) 暴力:

for(int l=1;l<=n;l++)
{
    for(int r=l;r<=n;r++)
    {
        int res=0;
        for(int i=l;i<=r;i++)
            res+=(i-l+1)*a[i];
        ans=max(ans,res);
    }
}
cout<<ans<<'\n';

然后发现往右扩大一个数字是简单的,遂有 O(n^2) dp:

```cpp for(int l=1;l<=n;l++) { for(int r=l;r<=n;r++) { dp[l][r]=dp[l][r-1]+(r-l+1)*a[r]; ans=max(ans,dp[l][r]); } } ``` 但这样不够优,原因就在这个 $(r-l+1)\times a_r$ 上。 每个结果只和前一位有关,就只能递推求解。 再观察之前能优化的形式,所有状态都有一个具体的从之前任意一个状态转移来的式子,每次都是从之前的所有状态选择一个最优的来转移。 那怎么把这个东西用一个全局适用公式来描述? 设 $sum_i$ 表示 $a_i$ 的前缀和,$summ_i$ 表示 $a_i\times i$ 的前缀和。 那么 $[l,r]$ 这一段的价值可以表示为: $cost=(summ_r-summ_{l-1})-(sum_r-sum_{l-1})\times(l-1)

换成 r\implies i,\ l\implies j,然后外层循环枚举 i。

\begin{aligned} f_i&=\max\{(summ_i-summ_{j-1})-(sum_i-sum_{j-1})\times(j-1)\}\\ &=\max\{summ_i-summ_{j-1}-sum_i\times(j-1)+sum_{j-1}\times(j-1)\}\\ &=\max\{sum_{j-1}\times(j-1)-summ_{j-1}-sum_i\times(j-1)\}+summ_i\\ \end{aligned}
cin>>n;
for(int i=1;i<=n;i++)
{
    cin>>a[i];
    sum[i]=sum[i-1]+a[i];
    summ[i]=summ[i-1]+a[i]*i;
}
for(int i=1;i<=n;i++)
{
    int maxx=0;
    for(int j=1;j<i;j++)
        maxx=max(maxx,sum[j-1]*(j-1)-summ[j-1] - sum[i]*(j-1));
    ans=max(ans,maxx+summ[i]);
}
cout<<ans<<'\n';
sum_{j-1}\times(j-1)-summ_{j-1}\implies y,\ sum_i\implies k,\ (j-1)\implies x

取 \max,维护上凸包。

但是 k 不是递增的,所以用二分。

#include<bits/stdc++.h>
#define int long long
#define pr pair<int,int>
#define qy(FILE) freopen(FILE".in","r",stdin);freopen(FILE".out","w",stdout);
using namespace std;
const int N=2e5+5,INF=0x3f3f3f3f3f3f3f3f;
int n,a[N],ans;
int sum[N],summ[N];
struct node{int x,y;};
vector<node>q;
int ask(node a,node b,node c)
{
    return (__int128)(b.y-a.y)*(c.x-b.x) <= (__int128)(c.y-b.y)*(b.x-a.x);
}
int query(int k)
{
    int l=0,r=max(0ll,(int)q.size()-1);
    while(l+1<r)
    {
        int mid=(l+r)>>1;
        node a=q[mid],b=q[mid+1];
        if(a.y-(__int128)a.x*k<b.y-(__int128)b.x*k) l=mid;
        else r=mid;
    }
    node a=q[l],b=q[r];
    if(a.y-(__int128)a.x*k>b.y-(__int128)b.x*k) return l;
    else return r;
}
signed main()
{
    // qy("q");
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        sum[i]=sum[i-1]+a[i];
        summ[i]=summ[i-1]+a[i]*i;
    }
    q.push_back({0,0});
    for(int i=1;i<=n;i++)
    {
        while(q.size()>=2&&ask(q[q.size()-2],q[q.size()-1],{i-1,sum[i-1]*(i-1)-summ[i-1]}))
            q.pop_back();
        q.push_back({i-1,sum[i-1]*(i-1)-summ[i-1]});
        int k=sum[i];
        int now=query(k);
        ans=max(ans,q[now].y-k*q[now].x+summ[i]);
    }
    cout<<ans<<'\n';
    return 0;
}

AT_dp_z Frog 3

先写个 O(n^2)。

cin>>n>>c;
for(int i=1;i<=n;i++) cin>>h[i];
memset(dp,0x3f,sizeof(dp));
dp[1]=0;
for(int i=2;i<=n;i++)
    for(int j=1;j<i;j++)
        dp[i]=min(dp[i],dp[j]+(h[i]-h[j])*(h[i]-h[j])+c);
cout<<dp[n]<<'\n';

拆公式:

\begin{aligned} dp_i&=\min\{dp_j+(h_i-h_j)^2+c\}\\ &=\min\{dp_j+h_i^2-2h_ih_j+h_j^2+c\}\\ &=\min\{dp_j+h_j^2-2h_ih_j\}+h_i^2+c\\ \end{aligned} dp_j+h_j^2\implies y,\ 2h_i\implies k,\ h_j\implies x

取 \min,维护下凸包。

```cpp #include<bits/stdc++.h> #define int long long #define pr pair<int,int> #define qy(FILE) freopen(FILE".in","r",stdin);freopen(FILE".out","w",stdout); using namespace std; const int N=2e5+5,INF=0x3f3f3f3f3f3f3f3f; int n,c,h[N],dp[N]; struct node{int x,y;}; vector<node>q; int get(node a,int k) { return a.y-k*a.x; } int ask(node a,node b,node c) { return 1.0*(b.y-a.y)/(b.x-a.x) >= 1.0*(c.y-b.y)/(c.x-b.x); } signed main() { // qy("q"); ios::sync_with_stdio(false); cin.tie(0);cout.tie(0); cin>>n>>c; for(int i=1;i<=n;i++) cin>>h[i]; memset(dp,0x3f,sizeof(dp)); dp[1]=0; int now=0; q.push_back({h[1],dp[1]+h[1]*h[1]}); for(int i=2;i<=n;i++) {//=\min(dp_j+h_j^2-2h_ih_j)+h_i^2+c; //dp_j+h_j^2⟹y , 2h_i⟹k , h_j⟹x int k=2*h[i]; while(now+1<(int)q.size()&&get(q[now],k)>=get(q[now+1],k)) now++; dp[i]=get(q[now],k)+h[i]*h[i]+c; node tmp={h[i],dp[i]+h[i]*h[i]}; while(q.size()>=2&&ask(q[q.size()-2],q[q.size()-1],tmp)) q.pop_back(); q.push_back(tmp); now=min(now,(int)q.size()-1); } cout<<dp[n]<<'\n'; return 0; } ``` # [忘情](https://www.luogu.com.cn/problem/P4983) 斜率优化 dp + wqs 二分。 一上来就看到公式,那第一步肯定是化简。 $$ \begin{aligned} \dfrac{\left(\sum_{i=1}^n x_i\times\overline{x}+x\right)^2}{\overline{x}^2} &=\dfrac{\left(\left(\sum_{i=1}^n x_i+1\right)\times\overline{x}\right)^2}{\overline{x}^2}\\ &=\left(\sum_{i=1}^n x_i+1\right)^2\\ \end{aligned} $$ 先不考虑 $m$,写一个 dp。 设 $sum_i=\sum_{k=1}^i x_k$。 则原式化简为 $(sum_r-sum_{l-1}+1)^2$。 $$ \begin{aligned} dp_i&=\min\{dp_j+(sum_i-sum_j+1)^2\}\\ &=\min\{dp_j-2sum_j+sum_j^2-2sum_i\cdot sum_j\}+sum_i^2+2sum_i+1\\ \end{aligned} $$ $dp_j-2sum_j+sum_j^2\implies y,\ 2sum_i\implies k,\ sum_j\implies x

取 \min,sum_i 递增,维护下凸包。

#include<bits/stdc++.h>
#define int long long
#define pr pair<int,int>
#define qy(FILE) freopen(FILE".in","r",stdin);freopen(FILE".out","w",stdout);
using namespace std;
const int N=2e5+5,INF=0x3f3f3f3f3f3f3f3f;
int n,m,a[N],sum[N],dp[N];
struct node{int x,y;};
vector<node>q;
int get(node a,int k)
{
    return a.y-k*a.x;
}
int ask(node a,node b,node c)
{
    return 1.0*(b.y-a.y)/(b.x-a.x) >= 1.0*(c.y-b.y)/(c.x-b.x);
}
signed main()
{
    // qy("q");
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>a[i],sum[i]=sum[i-1]+a[i];
    int now=0;
    q.push_back({0,0});
    for(int i=1;i<=n;i++)
    {//dp_j-2*sum_j+sum_j^2⟹y , 2*sum_i⟹k , sum_j⟹x
        int k=2*sum[i];
        while(now+1<(int)q.size()&&get(q[now],k)>=get(q[now+1],k))
            now++;
        dp[i]=get(q[now],k)+sum[i]*sum[i]+2*sum[i]+1;
        node tmp={sum[i],dp[i]-2*sum[i]+sum[i]*sum[i]};
        while(q.size()>=2&&ask(q[q.size()-2],q[q.size()-1],tmp))
            q.pop_back();
        q.push_back({tmp});
        now=min(now,(int)q.size()-1);
    }
    cout<<dp[n]<<'\n';
    return 0;
}

这就求出了 m=1 的情况。

再加上 wqs 二分,即可求出答案。

#include<bits/stdc++.h>
#define int long long
#define pr pair<int,int>
#define qy(FILE) freopen(FILE".in","r",stdin);freopen(FILE".out","w",stdout);
using namespace std;
const int N=2e5+5,INF=0x3f3f3f3f3f3f3f3f;
int n,m,a[N],sum[N],dp[N],cnt[N];
struct node{int x,y,cnt;};
vector<node>q;
int get(node a,int k)
{
    return a.y-k*a.x;
}
int ask(node a,node b,node c)
{
    return (__int128)(b.y-a.y)*(c.x-b.x) >= (__int128)(c.y-b.y)*(b.x-a.x);
}
int check(int d)
{
    q.clear();
    int now=0;
    q.push_back({0,0,0});
    for(int i=1;i<=n;i++)
    {//dp_j-2*sum_j+sum_j^2⟹y , 2*sum_i⟹k , sum_j⟹x
        int k=2*sum[i];
        while(now+1<(int)q.size()&&get(q[now],k)>=get(q[now+1],k))
            now++;
        dp[i]=get(q[now],k)+sum[i]*sum[i]+2*sum[i]+1-d;
        cnt[i]=q[now].cnt+1;
        node tmp={sum[i],dp[i]-2*sum[i]+sum[i]*sum[i],cnt[i]};
        while(q.size()>=2&&ask(q[q.size()-2],q[q.size()-1],tmp))
            q.pop_back();
        q.push_back(tmp);
        now=min(now,(int)q.size()-1);
    }
    return cnt[n];
}
signed main()
{
    // qy("forget");
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>a[i],sum[i]=sum[i-1]+a[i];
    int l=-1e16,r=0,mid;
    while(l+1<r)
    {
        mid=(l+r)>>1;
        if(check(mid)<m) l=mid;
        else r=mid;
    }
    check(r);cout<<dp[n]+r*m;
    return 0;
}

update:

2026/11/20 :添加\min,\max等正体,补全题目传送门。

2026/11/22 :将连等式用 aligned 对齐。

(希望管理大大通过😭😭😭)