历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

斜率优化 DP

作者：

zrzzrz , 2024-10-29 14:02:33 , 所有人可见 , 阅读 9

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;
}