斜率优化学习笔记

paulpao · 2026-07-23 21:08:23 · 算法·理论

前言

前置知识：单调队列，李超线段树。

对于DP的经典模型：dp_i=\min_{L(i)\le j \le R(i)}(dp_j+val(i,j))，当 val 中每一项都仅与 i,j 中的一个有关时，我们可以把带 i 的项全部提出来，对于带 j 的项，使用如单调队列，线段树等数据结构优化DP。

如果有与 i,j 的乘积相关的项，就可以使用斜率优化。

引入

题目描述

即

转化成线段了，直接上李超。

Code

#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
int n,lans=0;
long long a,b,c; 
const int N=1e6+5,V=1e6+5;
int ls[N],ys[N];
int x[N],sum[N];
long long dp[N];
struct line{
    long long k,b;
}l[N];
inline long long cal(line ll,int x){
    return ll.k*x+ll.b;
}
struct Node{
    int l,r; 
    line bst;
    int id;
}tr[8*V];
line e={0,-(long long)1e18};
inline bool cmp(int i,int id){
    int mid=ys[(tr[i].l+tr[i].r)>>1];
    if(cal(tr[i].bst,mid)<cal(l[id],mid) or (cal(tr[i].bst,mid)-cal(l[id],mid)==0&&id<tr[i].id)){
        return 1;
    }
    return 0;
}
inline void build(int i,int l,int r){
    tr[i]={l,r};
    tr[i].bst=e;
    tr[i].id=0;
    if(l==r){
        return;
    }
    int mid=(l+r)>>1;
    build(2*i,l,mid);
    build(2*i+1,mid+1,r);
}
inline void modify(int i,int id){
    line tl=l[id];
    int tid=id;
    if(tr[i].l==tr[i].r){
        if(cmp(i,id)){
            tr[i].bst=l[id];
            tr[i].id=id;
        }
        return;
    }
    if(cmp(i,id)){
        swap(tr[i].bst,tl);
        swap(tr[i].id,tid);
    }

    if(cal(tl,ys[tr[i].l])>cal(tr[i].bst,ys[tr[i].l])){
        modify(2*i,tid);
    }
    else if(cal(tl,ys[tr[i].r])>cal(tr[i].bst,ys[tr[i].r])){
        modify(2*i+1,tid);
    }
}
inline void update(int i,int l,int r,int id){
    if(tr[i].l>r or tr[i].r<l) return;
    if(l<=tr[i].l && tr[i].r<=r){
        modify(i,id);
        return;
    }
    update(2*i,l,r,id);
    update(2*i+1,l,r,id);
}
inline long long query(int i,int pos){
    int pos2=ys[pos];
    long long ans=cal(tr[i].bst,pos2);
    if(tr[i].l==tr[i].r){
        return ans;
    }
    int mid=ys[(tr[i].l+tr[i].r)>>1];
    if(pos2<=mid){
        long long la=query(2*i,pos);
        return max(la,ans);
    }
    else if(pos2>mid){
        long long la=query(2*i+1,pos);
        return max(la,ans); 
    }
}
int tot=0;
inline void add(int x0,int y0,int x1,int y1){
    if(x0>x1){
        swap(x0,x1);
        swap(y0,y1);
    }
    tot++;
    if(x0==x1){
        l[tot].k=0;
        l[tot].b=max(y0,y1);
        update(1,x0,x1,tot);
        return;
    }
    l[tot].k=(int)(y0-y1)/(int)(x0-x1);
    l[tot].b=(int)y0-(int)l[tot].k*x0; 
    update(1,x0,x1,tot);
}

const int mod=1e9; 
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0); 
    cin>>n;
    cin>>a>>b>>c;
    for(int i=1;i<=n;i++){
        cin>>x[i];
        sum[i]=sum[i-1]+x[i];
        ls[i]=sum[i];
    }

    sort(ls+1,ls+n+1);
    int mm=unique(ls+1,ls+n+1)-ls-1;
    for(int i=1;i<=n;i++){
        sum[i]=lower_bound(ls+1,ls+mm+1,sum[i])-ls;
    }
    for(int i=1;i<=mm;i++){
        ys[i]=ls[i];
    }
    build(1,1,mm);

    dp[0]=0;
    l[0]={0,0};
    modify(1,0);
    for(int i=1;i<=n;i++){
        dp[i]=a*ys[sum[i]]*ys[sum[i]]+b*ys[sum[i]]+c+query(1,sum[i]);
        l[i]={-2*a*ys[sum[i]],dp[i]+a*ys[sum[i]]*ys[sum[i]]-b*ys[sum[i]]};
        modify(1,i);
     //   cout<<dp[i]<<' ';
    }
    cout<<dp[n];
    return 0;
}

评注

如果读者初步理解了斜率优化，应当可以轻松解决。

再来一道需要一些推理的题

P4360 锯木厂选址

题目描述

从山顶上到山底下沿着一条直线种植了 n 棵老树。当地的人们决定把他们砍下来。为了不浪费任何一棵木材，树被砍倒后要运送到锯木厂。

木材只能朝山下运。山脚下有一个锯木厂。另外两个锯木厂将新修建在山路上。你必须决定在哪里修建这两个锯木厂，使得运输的费用总和最小。假定运输每公斤木材每米需要一分钱。

你的任务是编写一个程序，从输入文件中读入树的个数和他们的重量与位置，计算最小运输费用。