浅谈 - 斜率优化dp
hemingxi_2030 · · 算法·理论
点击此处传送至【博客园】食用体验更佳(有动图)
CF1083E The Fair Nut and Rectangles
先把矩形按
因为没有嵌套的矩形,所以容易得出新加入一个矩形的面积为
设
状态转移方程为:
易得
#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 进行优化。
因为涉及到取
再观察一下一次函数标准形式:
这能说明什么?
对每个
那怎么找到最大的值?
暴力做法是:对于每个
但这道题有一个性质:因为不存在嵌套的矩形,所以将
要想斜距最大,这条线必须是所有点连接而成的图形的切线。
而随着斜率变小,当前是切线的这个点的之前所有点一定都会经过这个图形,都不可能是切线。
如图,假设此时红线是切线,当斜率变大时,蓝线一定不会是切线。
当红线越过线段
所以,切线所属的点一定是单调不减一直往后移动的。
可以维护一个全局
以下是具体过程:
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=min(now,(int)q.size()-1) 这句话。
它的作用是:还看上图,当
因为只有当直线斜率大于 AB 时,放到 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
仿照上题,一样的套路,先写个
为了使
看到这里,是不是想直接搬第一题模版了?但是有两点需要注意。
- 本题 dp 为二维。
发现
- 本题是取
\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
答案取
代码如下:
#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;
}
时间复杂度:
part 4
与 part 3 不同的是,
这说明
回想一下,在保证单调性的情况下,我们只需要维护
但是现在单调性消失了,我们就必须维护整个凸壳,
还是之前那句话,要找到一条线,使得斜率等于
怎么找切线?
发现在这个凸壳里,越靠近切线经过的点,斜距越小,反之就越大。
先钦定选择一个点。如果它左边的点所在直线的斜距大于这个点,那就说明切点一定在这个点的右边,否则就在左边。
这不就是裸的二分吗!
根据刚才的思路,把找
#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;
}
时间复杂度:
CF319C Kalila and Dimna in the Logging Industry
设
如果砍倒了第
易得状态转移方程为:
代码:
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';
优化成
因为取
然后就是模版。
代码:
#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
先写一个
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';
然后发现往右扩大一个数字是简单的,遂有
换成
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';
取
但是
#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
先写个
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';
拆公式:
取
取
#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;
}
这就求出了
再加上 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 对齐。
(希望管理大大通过😭😭😭)