AcWing
  • 首页
  • 课程
  • 题库
  • 更多
    • 竞赛
    • 题解
    • 分享
    • 问答
    • 应用
    • 校园
  • 关闭
    历史记录
    清除记录
    猜你想搜
    AcWing热点
  • App
  • 登录/注册

斜率优化 DP

作者: 作者的头像   zrzzrz ,  2024-10-29 14:02:33 ,  所有人可见 ,  阅读 17


1


1

算法内容

对于形如 $b(i)=\min\limits_{j<i}\big\{y(j)-k(i)x(j)\big\}$ 的动态规划转移式子,可以考虑斜率优化。

称 $i$ 为「待决策点」,$j$ 为「决策点」。

$k(i),x(j)$ 均单调

单调队列维护凸壳即可。

// AT_dp_z Frog 3
#include <bits/stdc++.h>
using namespace std;
#define y(j) (f[j]+1ll*h[j]*h[j]+C)
#define k(i) 2*h[i]
#define x(j) h[j]
int n,h[200005],q[200005],l=1,r;
long long C,f[200005];
long double slope(int u,int v){
    if (x(u)==x(v)) return y(v)>y(u)?1e18:-1e18;
    return (y(v)-y(u))*1.0/(x(v)-x(u));
}
int main(){
    scanf("%d%lld",&n,&C);
    for (int i=1;i<=n;i++) scanf("%d",&h[i]);
    q[++r]=1;
    for (int i=2;i<=n;i++){
        while (l<r&&slope(q[l],q[l+1])<=k(i)) l++;
        int j=q[l];
        f[i]=y(j)-1ll*k(i)*x(j)+1ll*h[i]*h[i];
        while (l<r&&slope(q[r-1],q[r])>=slope(q[r],i)) r--;
        q[++r]=i;
    }
    printf("%lld\n",f[n]);
    return 0;
}

仅 $x(j)$ 单调

寻找最优决策点时运用二分。

// [SDOI2012] 任务安排
#include <bits/stdc++.h>
using namespace std;
#define y(j) (f[j]-1ll*s*c[j])
int n,s,t[300005],c[300005],q[300005],l=1,r;
long long f[300005];
double slope(int u,int v){
    if (c[u]==c[v]) return y(v)>y(u)?1e18:-1e18;
    return (y(v)-y(u))*1.0/(c[v]-c[u]);
}
int search(int l,int r,int k){
    while (l<r){
        int Mid=(l+r)>>1;
        if (Mid<r&&slope(q[Mid],q[Mid+1])<=k) l=Mid+1;
        else r=Mid;
    }
    return q[l];
}
int main(){
    scanf("%d%d",&n,&s);
    for (int i=1;i<=n;i++) scanf("%d%d",&t[i],&c[i]),t[i]+=t[i-1],c[i]+=c[i-1];
    for (int i=1;i<=n;i++){
        f[i]=1ll*c[i]*t[i]+1ll*s*c[n];
        if (l<=r){
            int j=search(l,r,t[i]);
            f[i]=min(f[i],f[j]+1ll*(c[i]-c[j])*t[i]+1ll*s*(c[n]-c[j]));
        }
        while (l<r&&slope(q[r-1],q[r])>=slope(q[r],i)) r--;
        q[++r]=i;
    }
    printf("%lld\n",f[n]);
    return 0;
}

$k(i),x(j)$ 均不单调

CDQ 分治

由于需要保证待决策点的 $k(i)$ 单调递增,决策点的 $x(j)$ 单调递增,则若当前处理的区间为 $[l,r]$,需满足 $[l,\text{Mid}]$ 的 $x$ 单调递增,$[\text{Mid}+1,r]$ 的 $k$ 单调递增。

因此,在全局按 $k$ 排序后,函数 $\text{CDQ}(l,r)$ 的递归过程如下:

  • 若 $l=r$,直接返回。
  • 否则,将 $[l,r]$ 按 $i$ 排序。
  • 处理 $\text{CDQ}(l,\text{Mid})$。
  • 用单调队列维护 $[l,\text{Mid}]$ 的凸壳。
  • 根据单调队列决策 $[\text{Mid}+1,r]$。
  • 处理 $\text{CDQ}(\text{Mid}+1,r)$。
  • 按照 $x$ 对 $[l,r]$ 进行归并排序。

$O(n\log n)$。

// [CEOI2017] Building Bridges
#include <bits/stdc++.h>
using namespace std;
#define y(j) (f[j]+1ll*h[j]*h[j]-s[j])
#define k(i) 2*h[i]
#define x(j) h[j]
int n,h[100005],q[100005],a[100005],t[100005];
long long f[100005],s[100005];
long double slope(int u,int v){
    if (x(u)==x(v)) return y(v)>y(u)?1e18:-1e18;
    return (y(v)-y(u))*1.0/(x(v)-x(u));
}
void CDQ(int L,int R){
    if (L==R) return;
    int Mid=(L+R)>>1,p1=L,p2=Mid+1;
    for (int i=L;i<=R;i++)
        if (a[i]<=Mid) t[p1++]=a[i];
        else t[p2++]=a[i];
    for (int i=L;i<=R;i++) a[i]=t[i];
    CDQ(L,Mid);
    int l=1,r=0;
    for (int i=L;i<=Mid;i++){
        while (l<r&&slope(q[r-1],q[r])>=slope(q[r],a[i])) r--;
        q[++r]=a[i];
    }
    for (int i=Mid+1;i<=R;i++){
        while (l<r&&slope(q[l],q[l+1])<=k(a[i])) l++;
        int j=q[l];
        f[a[i]]=min(f[a[i]],f[j]+1ll*(h[a[i]]-h[j])*(h[a[i]]-h[j])+s[a[i]-1]-s[j]);
    }
    CDQ(Mid+1,R);
    p1=L,p2=Mid+1;
    int p=L;
    for (;p1<=Mid&&p2<=R;)
        if (x(a[p1])<x(a[p2])) t[p++]=a[p1++];
        else t[p++]=a[p2++];
    for (;p1<=Mid;) t[p++]=a[p1++];
    for (;p2<=R;) t[p++]=a[p2++];
    for (int i=L;i<=R;i++) a[i]=t[i];
}
int main(){
    memset(f,0x3f,sizeof f);
    scanf("%d",&n);
    for (int i=1;i<=n;i++) scanf("%d",&h[i]);
    for (int i=1;i<=n;i++) scanf("%lld",&s[i]),s[i]+=s[i-1],a[i]=i;
    sort(a+1,a+n+1,[&](int a,int b){return k(a)<k(b);});
    f[1]=0,CDQ(1,n);
    printf("%lld\n",f[n]);
    return 0;
}

李超线段树

树上转移($x(j)$ 在深度上单调)

在 $\text{dfs}$ 时,维护单调队列,暴力出队 / 入队并在递归结束后撤销的操作会被卡到 $O(n^2)$,瓶颈在出队。

考虑优化,发现出队可以二分,于是可以做到 $O(n\log n)$。

// 洛谷 P3994 高速公路(加上每个点只能前往祖先的限制)
#include <bits/stdc++.h>
using namespace std;
#define y(j) f[j]
#define k(i) p[i]
#define x(j) depth[j]
int n,p[1000005],Q[1000005],head[1000005],ver[1000005],edge[1000005],nxt[1000005],tot,l=1,r=1,q[1000005];
long long depth[1000005],f[1000005];
void add(int u,int v,int w){
    ver[++tot]=v,edge[tot]=w;
    nxt[tot]=head[u],head[u]=tot;
}
long double slope(int u,int v){
    if (x(u)==x(v)) return y(u)<y(v)?1e18:-1e18;
    return (y(v)-y(u))*1.0/(x(v)-x(u));
}
int solve(int l,int r,int x){
    while (l<r){
        int Mid=(l+r)>>1;
        if (slope(q[Mid],q[Mid+1])<=k(x)) l=Mid+1;
        else r=Mid;
    }
    return q[l];
}
int calc(int l,int r,int x){
    while (l<r){
        int Mid=(l+r)>>1;
        if (slope(q[Mid],q[Mid+1])>=slope(q[Mid+1],x)) r=Mid;
        else l=Mid+1;
    }
    return l;
}
void dfs(int u,int fa){
    int pre,r0;
    if (u>1){
        int j=solve(l,r,u);
        f[u]=f[j]+p[u]*(depth[u]-depth[j])+Q[u];
        r0=r,r=calc(l,r,u);
        pre=q[r+1];
        q[++r]=u;
    }
    for (int i=head[u];i;i=nxt[i]){
        int v=ver[i],w=edge[i];
        if (v==fa) continue;
        depth[v]=depth[u]+w,dfs(v,u);
    }
    if (u>1) q[r--]=pre,r=r0;
}
int main(){
    scanf("%d",&n);
    for (int i=2,u,w;i<=n;i++) scanf("%d%d%d%d",&u,&w,&p[i],&Q[i]),add(u,i,w);
    q[1]=1,dfs(1,1);
    for (int i=2;i<=n;i++) printf("%lld\n",f[i]);
    return 0;
}

例题(「*」为自己想出来的题)

$1\text{D}$ 双单增

*洛谷 P2900 [USACO08MAR] Land Acquisition G

将所有的 $(w_i,l_i)$ 化为二维平面 $wOl$ 上的一个点,则每个点与原点 $O$ 会形成一个矩形。

若一个矩形为另一个矩形的子矩形,显然不会选择该矩形。

则 $l$ 随 $w$ 增加而单调递减。

因此 $f_i=\min\limits_{j<i}\big\{f_{j}-w_i\cdot (-l_{j+1})\big\}$,裸斜率优化。

$2\text{D}$ 双单增

*洛谷 P4072 [SDOI2016] 征途

推式子发现 $v\times m^2=m(\sum v_i^2)-(\sum v_i)^2$,则不考虑常数每段行程对答案的贡献为 $v_i^2$。

$f_{i,d}=\min\limits_{j<i}\big\{f_{j,d-1}+(\text{sumv}_i-\text{sumv}_j)^2\big\}$,直接按照 $d$ 为「阶段」,进行斜率优化 $\text{DP}$ 即可。

效率为 $O(nm)$。

*CF311B Cats Transport

考虑将每个铲屎官「连续地」带走猫子的过程转化为一次性带走所有能带走的猫子。

那么只需要让 $T_i\leftarrow T_i-\sum\limits_{j=2}^iD_j$,则变为每个铲屎官可以带走一段时间内的所有猫子,直接斜率优化 $\text{DP}$ 即可。

*洛谷 P3648 [APIO2014] 序列分割

考虑如何不依赖分割顺序地统计答案。

注意到,若设 $s_i=\sum\limits_{j=1}^ia_i,f(l,r)=(s_r-s_{l-1})^2$,答案即为 $\dfrac{f(1,n)-\sum\limits_{i=1}^{k+1}f(l_i,r_i)}2$。

4 评论


用户头像
Conan15   2024-10-29 14:46      2    踩      回复

/bx/bx/bx


用户头像
Conan15   2024-10-31 17:16      1    踩      回复

你的李超线段树 咕咕咕,咕咕咕,咕咕咕咕咕呢()

用户头像
zrzzrz   2024-10-31 20:32      1    踩      回复

学了再写/ww

用户头像
Conan15   2024-10-31 21:05    回复了 zrzzrz 的评论         踩      回复

(翻译:咕不出来了。)


App 内打开
你确定删除吗?
1024
x

© 2018-2025 AcWing 版权所有  |  京ICP备2021015969号-2
用户协议  |  隐私政策  |  常见问题  |  联系我们
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标 qq图标
请输入绑定的邮箱地址
请输入注册信息