Skip to content

斜率优化dp

1) 转移方程类似 \(f[i]=a[i]+b[j],j<=i\) 的可以用单调队列维护\(i\)前面的一段合法区间的最值，从而将\(O(n^2)\)的转移优化到\(O(n)\)

2) 转移方程类似\(f[i]=a[i]* b[j]+c[i]+d[j]\)就不能只是单调队列优化了，我们需要单调队列+斜率优化

先来一道例题会比较好理解

P3195

经典斜率优化。 $$

转移方程为f[i]=f[j]+(i-j-1+s[i]-s[j]-L)\s[i]表示前缀和。\

设a(i)=s[i]+i,b(i)=a(i)+L+1\那么原式变为f[i]=f[j]+(a(i)-b(j))^2\ 移项得\

2a(i)* b(j) +f[i]-a(i)^2=f[j]+b(j)^2\

那么可以看成k=2a(i),x=b(j),y=(f[j]+b(j)^2),b=f[i]-a(i)^2的直线y=kx+b $$

对于每个直线（1~n）,都有斜率\(2a(i)\)单调递增，而我们要求截距\(f[i]-a(i)^2\)的最小值，也就是当我们维护一个下凸包时，直线的斜率刚好满足\(slope(P_{j},P_{j+1})>k\)时的点\(j\)即为我们要的\(f[j]\)（可以理解为相切）

因此用单调队列维护下凸包上的点。

1) \(slope(P_{head},P_{head+1}\leq k):++head\),弹出前端的点，因为不"相切"

2) \(slope(P_{tail-1},P_i)<slope(P_{tail-1},P_{tail}):--tail\),说明\(P_{tail}\)不再是凸包上的点，不需要就弹出

#include<iostream> 
#include<cstdio>
#include<cstring>
#define int long long 
using namespace std;
typedef double db;
const int N=5e4+10;
int C[N],s[N],q[N];
int n,L,head,tail;
db f[N];
db a(int i){
    return (db)(s[i]+i);
}
db b(int i){
    return (db)(s[i]+i+L+1);
}
db slope(int u,int v){
    db yu=f[u]+b(u)*b(u),yv=f[v]+b(v)*b(v),xu=b(u),xv=b(v);
    return (yu-yv)/(xu-xv);
}
void dp(){
    head=tail=1;
    q[head]=0;
    for(int i=1;i<=n;++i){
        while(head<tail && slope(q[head],q[head+1])< 2*a(i)) ++head;
        f[i]=f[q[head]]+(a(i)-b(q[head]))*(a(i)-b(q[head]));
        while(head<tail && slope(q[tail-1],q[tail])>slope(q[tail-1],i)) --tail;
        q[++tail]=i;    
    }
    printf("%lld",(long long)(f[n]));
}
signed main(){
    scanf("%lld%lld",&n,&L);
    for(int i=1;i<=n;++i) scanf("%lld",&C[i]),s[i]=s[i-1]+C[i];
    dp();
    return 0;
}

线段树优化dp

P1295 & P1848

相同类型的题,就只讲P1295吧，还简单一点。

暴力\(O(n^2)\)转移：\(f[i]=f[j]+(\max_{k=j+1}^ih_k)(\sum_{k=j+1}^ih_k\leq m)\)

对于每个点，可以首先\(O(n\log n)\)二分求出它最靠左且满足长度\(\leq m\)的端点位置\(prelen[i]\),还有\(O(n)\)单调栈求出前一个比他大的数的位置 \(premax[i]\).

然后，对于当前点\(i\)，我们需要将前\(i-1\)个点的\(f[i]\)加上\(i\)产生的"贡献"后取最小，求出\(f[i]\).

所以，我们需要在求\(f[k]\)之前在\(k\)的位置单点修改\(f[k-1]\),表示如果取\([k,i]\)这段区间的话要加上\(f[k-1]\).

然后就是常见的操作，对于所有大于\(h[i]\)的点是没有影响的，所以将\([premax[i],i]\)修改为\(h[i]\).

最后，查询\([prelen[i],i]\)这段区间的最小值即可。

显然这个过程可以用线段树维护。

注意\(f\)是单点修改，不需要\(tag\),而\(ans\)需要用\(tag+f\)得到。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stack>
#define int long long 
#define ls i<<1
#define rs i<<1|1
#define mid (l+r>>1)
using namespace std;
typedef pair<int,int> PI;
const int N=1e5+10,INF=1e18;
int n,m;
int a[N],premax[N],prelen[N],s[N],f[N];
struct tree{
    int tag,l,r,f,ans;
}tre[N<<2];
void init(){
    stack<PI> q;
    for(int i=1;i<=n;++i){
        int pos=lower_bound(s,s+n+1,s[i]-m)-s+1;prelen[i]=pos;
    }
    for(int i=1;i<=n;++i){
        while(!q.empty() && q.top().first<a[i])q.pop();
        premax[i]=q.empty()?1:q.top().second+1;q.push(make_pair(a[i],i));
    }
}
void pushup(int i){
    tre[i].f=min(tre[ls].f,tre[rs].f);
    tre[i].ans=min(tre[ls].ans,tre[rs].ans);
}
void build(int i,int l,int r){
    tre[i].l=l,tre[i].r=r,tre[i].tag=0,tre[i].f=INF,tre[i].ans=INF;
    if(l==r)return;
    build(ls,l,mid);
    build(rs,mid+1,r);
    pushup(i);  
}
void pushdown(int i){
    int k=tre[i].tag;
    if(!k)return;
    tre[ls].tag=k,tre[ls].ans=tre[ls].f+k;
    tre[rs].tag=k,tre[rs].ans=tre[rs].f+k;
    tre[i].tag=0;
}
void add(int i,int pos,int k){
    int l=tre[i].l,r=tre[i].r;
    if(l==r){
        tre[i].f=k;return;
    }
    pushdown(i);
    if(pos<=mid)add(ls,pos,k);
    else add(rs,pos,k);
    pushup(i);
}
void change(int i,int el,int er,int k){
    int l=tre[i].l,r=tre[i].r;
    if(el<=l && r<=er){
        tre[i].ans=tre[i].f+k,tre[i].tag=k;
        return;
    }
    pushdown(i);
    if(el<=mid)change(ls,el,er,k);
    if(er>mid)change(rs,el,er,k);
    pushup(i);
}
int query(int i,int el,int er){
    int l=tre[i].l,r=tre[i].r;
    if(el<=l && r<=er) return tre[i].ans;
    pushdown(i);
    int ans=INF;
    if(el<=mid)ans=min(ans,query(ls,el,er));    
    if(er>mid)ans=min(ans,query(rs,el,er));
    return ans;
}

signed main(){
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;++i)scanf("%lld",&a[i]),s[i]=s[i-1]+a[i];
    build(1,1,n);
    init();
    for(int i=1;i<=n;++i){
        add(1,i,f[i-1]);
        if(premax[i]<=i)change(1,premax[i],i,a[i]);
        if(prelen[i]<=i)f[i]=query(1,prelen[i],i);
    }
    printf("%lld",f[n]);    
    return 0;
}
/*
4 9
1 6 3 5 1
*/
* 结论：线段树优化的题一般特点是连续取一点区间，再加上之前的贡献更新\(f[i]\)

CF833B

常见离线操作，对于\(a[i]\)只对它前一次出现的位置之后有影响。

而对于那个\(k\)段，可以每次建一次树，树中初始为\(f[l-1][k-1]\)。

然后就是标准线段树优化。

#include<iostream>
#include<cstdio>
#include<cstring>
#define ls i<<1
#define rs i<<1|1
#define int long long 
using namespace std;
const int N=4e4+10,K=55;
int f[K][N],pos[N],pre[N],tre[N<<2],tag[N<<2];
int n,k,t;
void pushup(int i){
    tre[i]=max(tre[ls],tre[rs]);
}
void pushdown(int i,int l,int r){
    int k=tag[i];
    if(!k)return;
    tag[ls]+=k;tag[rs]+=k;tre[ls]+=k;tre[rs]+=k;
    tag[i]=0;   
}
void build(int i,int l,int r,int now){
    tag[i]=0;
    if(l==r){
        tre[i]=f[now][l-1];
        return;
    }
    int mid=(l+r)>>1;
    build(ls,l,mid,now);
    build(rs,mid+1,r,now);
    pushup(i);
}
void change(int i,int l,int r,int el,int er,int k){
    if(el<=l && r<=er){
        tag[i]+=k;tre[i]+=k;
        return;
    }
    pushdown(i,l,r);
    int mid=(l+r)>>1;
    if(el<=mid) change(ls,l,mid,el,er,k);
    if(er>mid) change(rs,mid+1,r,el,er,k);
    pushup(i);
}
int query(int i,int l,int r,int el,int er){
    if(el<=l && r<=er) return tre[i];
    pushdown(i,l,r);
    int mid=(l+r)>>1,ans=0;
    if(el<=mid)ans=max(ans,query(ls,l,mid,el,er));
    if(er>mid)ans=max(ans,query(rs,mid+1,r,el,er));
    return ans;
}
signed main(){
    scanf("%lld%lld",&n,&k);
    for(int i=1;i<=n;++i)scanf("%lld",&t),pre[i]=pos[t]+1,pos[t]=i;
    for(int i=1;i<=k;++i){
        build(1,1,n,i-1);
        for(int j=1;j<=n;++j){
            change(1,1,n,pre[j],j,1);
            f[i][j]=query(1,1,n,1,j);
        }
    }
    printf("%lld",f[k][n]);
}