斜率优化DP 学习笔记

xujindong_ · 2024-10-28 11:31:05 · 个人记录

概述

斜率优化可以优化一类 1D / 1D 的动态规划，方程形如 f_i=\min f_j+A_i+B_j+C_iD_j（\max 类似）。也就是有且仅有一项是与 i 有关的东西和与 j 有关的东西的乘积。此时有两种理解：

将之前的所有 j 的 C_iD_j+B_j+f_j 看作一个一次函数，相当于有若干个一次函数 y=kx+b，找 x=C_i 处这些一次函数的最小值；

化成 f_j+B_j=-C_iD_j+f_i-A_i。令 y=f_j+B_j,k=C_i,x=-D_j,b=A_i-f_i。转移时相当于要在若干个点中找到一个点 (x,y) 使得经过这个点的的斜率为 k 的直线在 y 轴的截距最小。

对于第二种理解，需要维护出一个下凸包，每次用斜率为 k 的直线切这个凸包。当插入时 x 有序且查询的斜率有序，此时最优决策点有序且 x 有序，可以单调队列维护凸包，每次将答案之前的出队；若仅有 x 有序，需要单调栈维护凸包，每次二分。若都不有序，需要动态凸包或李超线段树（李超线段树为第一种理解）或 CDQ 分治。

例题

P3195

令 sum_i=\sum_{j=1}^i C_j+1,L\gets L+1，则 f_i=\min_{j=0}^{i-1}f_j+(s_i-s_j-L)^2。改写为 f_j+sum_j^2=2(s_i-L)s_j+f_i-(s_i-L)^2。由于 C_i 是正数，所以 x,k 单调递增，单调队列即可。

#include<bits/stdc++.h>
using namespace std;
int n,bp,fp,q[50005];
long long x,a[50005],f[50005];
double slope(int i,int j){
  return 1.0*(f[j]+a[j]*a[j]-f[i]-a[i]*a[i])/(a[j]-a[i]);
}
int main(){
  cin>>n>>x,x++;
  for(int i=1;i<=n;i++)cin>>a[i],a[i]+=a[i-1]+1;
  for(int i=1;i<=n;i++){
    while(bp<fp&&slope(q[bp],q[bp+1])<2*(a[i]-x))bp++;
    f[i]=f[q[bp]]+(a[i]-a[q[bp]]-x)*(a[i]-a[q[bp]]-x);
    while(bp<fp&&slope(q[fp-1],q[fp])>slope(q[fp],i))fp--;
    q[++fp]=i;
  }
  return cout<<f[n]<<'\n',0;
}

P2120

设 p 的前缀和为 sp，1\sim i 的产品运到 i 的代价为 sum_i，则 f_i=\min_{j=0}^{i-1}f_j+sum_i-sum_j-sp_j(x_i-x_j),f_j-sum_j+x_jsp_j=x_isp_j+f_i-sum_i。

注意一些细节：p_i 可能有 0，当 sp_i=sp_j 时比较 y，斜率为正无穷或负无穷。最后的答案是从最后一个有成品的工厂开始的最小值。

#include<bits/stdc++.h>
using namespace std;
int n,bp,fp,q[1000005];
long long x[1000005],p[1000005],c[1000005],sum[1000005],f[1000005],ans;
double slope(int i,int j){
  long long yj=f[j]-sum[j]+p[j]*x[j],yi=f[i]-sum[i]+p[i]*x[i];
  if(p[i]==p[j])return yj>yi?1e18:-1e18;
  return 1.0*(yj-yi)/(p[j]-p[i]);
}
int main(){
  cin>>n;
  for(int i=1;i<=n;i++)cin>>x[i]>>p[i]>>c[i],p[i]+=p[i-1],sum[i]=sum[i-1]+p[i-1]*(x[i]-x[i-1]);
  for(int i=1;i<=n;i++){
    while(bp<fp&&slope(q[bp],q[bp+1])<x[i])bp++;
    f[i]=f[q[bp]]+sum[i]-sum[q[bp]]-p[q[bp]]*(x[i]-x[q[bp]])+c[i];
    while(bp<fp&&slope(q[fp-1],q[fp])>slope(q[fp],i))fp--;
    q[++fp]=i;
  }
  ans=f[n];
  for(int i=n-1;i>=1&&p[i]==p[i+1];i--)ans=min(ans,f[i]);
  return cout<<ans<<'\n',0;
}

P2900

首先有用的地不会被另一块地严格包含。选出有用的地后，w 单调不升，l 单调不降。此时 f_{i}=\max_{j=0}^{i-1}f_j+w_{j+1}l_i,f_j=f_i-w_{j+1}l_i。令 x=-w_{j+1},y=f_j,k=l_i,b=f_i 即可。

#include<bits/stdc++.h>
using namespace std;
int n,cnt,bp,fp,q[50005];
long long f[50005];
struct node{
  long long x,y;
}a[50005],b[50005];
bool cmp(node a,node b){
  return a.x==b.x?a.y>b.y:a.x>b.x;
}
double slope(int i,int j){
  return 1.0*(f[j]-f[i])/(a[i+1].x-a[j+1].x);
}
int main(){
  cin>>n;
  for(int i=1;i<=n;i++)cin>>b[i].x>>b[i].y;
  sort(b+1,b+n+1,cmp);
  for(int i=1;i<=n;i++)if(b[i].y>a[cnt].y)a[++cnt]=b[i];
  n=cnt;
  for(int i=1;i<=n;i++){
    while(bp<fp&&slope(q[bp],q[bp+1])<a[i].y)bp++;
    f[i]=f[q[bp]]+a[q[bp]+1].x*a[i].y;
    while(bp<fp&&slope(q[fp-1],q[fp])>slope(q[fp],i))fp--;
    q[++fp]=i;
  }
  return cout<<f[n]<<'\n',0;
}

P5504

性质：划分出来的段的端点颜色相同，且等于这一段选择的颜色。否则若端点颜色不等于选择的颜色，将这一端不断向内缩直到相等一定不劣。

此时可以列出转移方程：f_i=\max_{0<j\leq i,s_i=s_j}f_{j-1}+a_j(cnt_i-cnt_j+1)^2。斜率优化，拆成 f_{j-1}+a_j(cnt_j-1)^2=2a_jcnt_i(cnt_j-1)+f_i-a_icnt_i^2。每个颜色分别维护。

有一个特殊的地方：这题要维护一个上凸包，查询斜率单调递增，相当于一个单调栈。因为被删除的点在之前已经更劣，因此只保留未被删除的点组成凸包是正确的。

#include<bits/stdc++.h>
using namespace std;
int n,cnt[10005];
long long a[100005],f[100005],p[100005];
vector<int>st[10005];
double slope(int i,int j){
  return 1.0*(f[j-1]+a[j]*(p[j]-1)*(p[j]-1)-f[i-1]-a[i]*(p[i]-1)*(p[i]-1))/(a[j]*p[j]-a[i]*p[i]);
}
int main(){
  cin>>n;
  for(int i=1;i<=n;i++)cin>>a[i],p[i]=++cnt[a[i]];
  for(int i=1;i<=n;i++){
    while(st[a[i]].size()>1&&slope(*----st[a[i]].end(),st[a[i]].back())<slope(st[a[i]].back(),i))st[a[i]].pop_back();
    st[a[i]].push_back(i);
    while(st[a[i]].size()>1&&slope(*----st[a[i]].end(),st[a[i]].back())<2*p[i])st[a[i]].pop_back();
    f[i]=f[st[a[i]].back()-1]+a[i]*(p[i]-p[st[a[i]].back()]+1)*(p[i]-p[st[a[i]].back()]+1);
  }
  return cout<<f[n]<<'\n',0;
}

AT_abc228_h

设最后出现的不同的数为 b_1,b_2,\cdots,b_k，显然最优是将 a 排序后分成 k 段，第 i 段变成 b_i，且 b_i 变成段中最大值显然更优。令 sum_i=\sum_{j=1}^i a_ic_i,sumc_i=\sum_{j=1}^i c_i，可以列出转移方程：f_i=\min_{j=0}^{i-1}f_j+a_i(sumc_i-sumc_j)-(sum_i-sum_j)+x。斜率优化，f_j+sum_j+x=a_isumc_j+f_i-a_isumc_i+sum_i。因为 a_i,sumc_j 都单调递增，可以单调队列维护凸包。

#include<bits/stdc++.h>
using namespace std;
int n,q[200005],bp,fp;
long long x,f[200005],sum[200005],sumc[200005];
struct node{
  long long a,c;
}a[200005];
bool cmp(node a,node b){
  return a.a<b.a;
}
double slope(int i,int j){
  return 1.0*(f[j]+sum[j]-f[i]-sum[i])/(sumc[j]-sumc[i]);
}
int main(){
  cin>>n>>x;
  for(int i=1;i<=n;i++)cin>>a[i].a>>a[i].c;
  sort(a+1,a+n+1,cmp);
  for(int i=1;i<=n;i++)sum[i]=sum[i-1]+a[i].a*a[i].c,sumc[i]=sumc[i-1]+a[i].c;
  for(int i=1;i<=n;i++){
    while(bp<fp&&slope(q[bp],q[bp+1])<a[i].a)bp++;
    f[i]=f[q[bp]]+a[i].a*(sumc[i]-sumc[q[bp]])-(sum[i]-sum[q[bp]])+x;
    while(bp<fp&&slope(q[fp-1],q[fp])>slope(q[fp],i))fp--;
    q[++fp]=i;
  }
  return cout<<f[n]<<'\n',0;
}

P5785

设 sf,st 为 f,t 的前缀和。不难设出 O(n^3) 的 DP，设 f_{i,j} 表示前 i 个分 j 段的答案，则 f_{i,j}=\min_{k=0}^{i-1}f_{k,j-1}(st_i+sj)(sf_i-sf_k)。

考虑换一个角度：每增加一段，后面的所有任务的用时增加 s。此时我们不再关心段数，有 f_i=\min_{j=0}^{i-1}f_j+st_i(sf_i-sf_j)+s(sf_n-sf_j)。

斜率优化，f_i=f_j+st_isf_i-st_isf_j+ssf_n-ssf_j,f_j-ssf_j=st_isf_j+f_i-st_isf_i-ssf_n。

注意 st_i 不是单调递增的，所以要单调栈上二分。注意特判斜率不存在的情况。

#include<bits/stdc++.h>
using namespace std;
int n,st[300005],top;
long long s,a[300005],b[300005],f[300005];
double slope(int i,int j){
  long long yj=f[j]-s*b[j],yi=f[i]-s*b[i];
  if(f[i]==f[j])return yj>yi?1e18:-1e18;
  return 1.0*(yj-yi)/(b[j]-b[i]);
}
int main(){
  cin>>n>>s;
  for(int i=1;i<=n;i++)cin>>a[i]>>b[i],a[i]+=a[i-1],b[i]+=b[i-1];
  for(int i=1;i<=n;i++){
    int l=0,r=top;
    while(l<r){
      int mid=(l+r)>>1;
      if(slope(st[mid],st[mid+1])<a[i])l=mid+1;
      else r=mid;
    }
    f[i]=f[st[l]]+s*(b[n]-b[st[l]])+a[i]*(b[i]-b[st[l]]);
    while(top&&slope(st[top-1],st[top])>slope(st[top],i))top--;
    st[++top]=i;
  }
  return cout<<f[n]<<'\n',0;
}

P2497

设接受半径为 R_i。假设 i 从 j 接受到信号，则 (x_i-x_j)^2+(R_i-r_j)^2=(R_i+r_j)^2，可得 R_i=\frac{(x_i-x_j)^2}{4r_j}。可以 DP，有 f_i=\min_{j=0}^{i-1}f_j+\frac{x_i-x_j}{2\sqrt{r_j}}+v_i。

斜率优化，有 f_j-\frac{x_j}{2\sqrt{r_j}}=-\frac{x_i}{2\sqrt{r_j}}+f_i-v_i。-\frac 1{2\sqrt{r_j}} 不单调，用李超树等方式维护即可。

#include<bits/stdc++.h>
using namespace std;
int n,tr[2000005],cnt;
long long m,x[500005],r[500005],v[500005],temp[500005];
double f[500005],k[500005],b[500005],ans=1e18;
bool check(int u,int v,int x){
  return k[u]*temp[x]+b[u]<k[v]*temp[x]+b[v];
}
void add(int pos,int nl,int nr,int g){
  int mid=(nl+nr)>>1;
  if(check(g,tr[pos],mid))swap(g,tr[pos]);
  if(check(g,tr[pos],nl))add(pos<<1,nl,mid,g);
  if(check(g,tr[pos],nr))add(pos<<1|1,mid+1,nr,g);
}
double query(int pos,int nl,int nr,int g){
  if(nl==nr)return k[tr[pos]]*temp[g]+b[tr[pos]];
  int mid=(nl+nr)>>1;
  double ans=k[tr[pos]]*temp[g]+b[tr[pos]];
  if(g<=mid)ans=min(ans,query(pos<<1,nl,mid,g));
  else ans=min(ans,query(pos<<1|1,mid+1,nr,g));
  return ans;
}
int main(){
  ios::sync_with_stdio(0),cin.tie(0),b[0]=1e18,cin>>n>>m;
  for(int i=1;i<=n;i++)cin>>x[i]>>r[i]>>v[i],temp[i]=x[i];
  sort(temp+1,temp+n+1),cnt=unique(temp+1,temp+n+1)-temp-1;
  for(int i=1;i<=n;i++)x[i]=lower_bound(temp+1,temp+cnt+1,x[i])-temp;
  for(int i=1;i<=n;i++)f[i]=i==1?v[i]:query(1,1,cnt,x[i])+v[i],k[i]=0.5/sqrt(r[i]),b[i]=f[i]-0.5*temp[x[i]]/sqrt(r[i]),add(1,1,cnt,i);
  for(int i=1;i<=n;i++)if(temp[x[i]]+r[i]>=m)ans=min(ans,f[i]);
  return cout<<setprecision(3)<<fixed<<ans<<'\n',0;
}

P4027

显然一次买卖必然用光当前所有的钱或券。设 f_i 为第 i 天最多持有多少现金，转移要么从第 i-1 天继承，要么在第 i 天发生卖出。枚举对应的买入在第 j 天，有 f_i=\max(f_{i-1},\max_{j=0}^{i-1}\frac{f_Jr_j}{r_ja_j+b_j}a_i+\frac{f_j}{r_ja_j+b_j}b_i)。

设 \frac{f_j}{r_ja_j+b_j}=c。对于第二种转移，为 f_i=cr_ja_i+cb_i，化为 \frac {f_i}{b_i}=cr_j\frac{a_i}{b_i}+c，用李超树等方式维护即可。

#include<bits/stdc++.h>
using namespace std;
int n,p[100005],cnt,tr[400005];
double x[100005],y[100005],r[100005],temp[100005],f[100005],k[100005],b[100005];
bool check(int u,int v,int x){
  return k[u]*temp[x]+b[u]>k[v]*temp[x]+b[v];
}
void add(int pos,int nl,int nr,int g){
  int mid=(nl+nr)>>1;
  if(check(g,tr[pos],mid))swap(g,tr[pos]);
  if(check(g,tr[pos],nl))add(pos<<1,nl,mid,g);
  if(check(g,tr[pos],nr))add(pos<<1|1,mid+1,nr,g);
}
double query(int pos,int nl,int nr,int g){
  if(nl==nr)return k[tr[pos]]*temp[g]+b[tr[pos]];
  int mid=(nl+nr)>>1;
  double ans=k[tr[pos]]*temp[g]+b[tr[pos]];
  if(g<=mid)ans=max(ans,query(pos<<1,nl,mid,g));
  else ans=max(ans,query(pos<<1|1,mid+1,nr,g));
  return ans;
}
int main(){
  cin>>n>>f[0];
  for(int i=1;i<=n;i++)cin>>x[i]>>y[i]>>r[i],temp[i]=x[i]/y[i];
  sort(temp+1,temp+n+1),cnt=unique(temp+1,temp+n+1)-temp-1;
  for(int i=1;i<=n;i++)p[i]=lower_bound(temp+1,temp+cnt+1,x[i]/y[i])-temp;
  for(int i=1;i<=n;i++)f[i]=max(f[i-1],query(1,1,cnt,p[i])*y[i]),k[i]=f[i]*r[i]/(r[i]*x[i]+y[i]),b[i]=f[i]/(r[i]*x[i]+y[i]),add(1,1,cnt,i);
  return cout<<setprecision(3)<<fixed<<f[n]<<'\n',0;
}

P2305