斜率优化 DP 入门

前言

本蒟蒻的第一道斜率优化 DP 前后卡了 3 小时…… 海星

有时候好不容易推出一个 DP 的式子,结果发现数据范围太大?

单调队列无法优化?

那就考虑斜率优化吧

[APIO2014] 序列分割

你正在玩一个关于长度为 的非负整数序列的游戏。这个游戏中你需要把序列分成 非空块。每次分裂一个块的贡献是那两个新的块的元素和的乘积。最大化贡献。

样例

Input

7 3
4 1 3 4 0 2 3

Output

108
1 3 5

说明

你可以通过下面这些操作获得 108 分:

初始时有一块 。在第 1 个元素后面分开,获得 分。
你现在有两块 。在第 3 个元素后面分开,获得 分。
你现在有三块 。在第 5 个元素后面分开,获得 分。

所以,经过这些操作后你可以获得四块 并获得 分。

DP 方程

把一个序列分成三段,得分满足 。因此发现,得分只与切的位置有关,与切的顺序无关。

既然不关心切的顺序,就把每次切的当做前 i 个中的第一次吧。 表示前 i 个数分 j​ 次的最大得分:

,我们可以得到:

直接转移,复杂度 .

单调队列?然而 就不好处理了

抽象出函数模型

斜率优化说简单点,就是对付 这种东西的。

我们知道, 对当前我们要求的 来说是一个常量,而 随决策 的变化而变化,是相对的变量

因此,面对常量乘变量这种形式,我们就将其抽象成数学的函数模型

先化一下方程式,我们暂且把 去掉:

观察这个等式:

  • 常量,而 变量
  • 转移的代价,而 是之前计算的子问题的最优解(决策值), 是要求解的问题
  • 相比较而言, 已知的(之前就计算好了),而 未知的(我们正在求啊)

我们对式子进行变形,将未知量,已知量分开,同时将常量与变量分开:

我们来说一些废话……

式子被分成三部分:

  • :未知量
  • :变量 常量;已知量
  • :变量;已知量

用已知量求解未知量是显然的思维方式,但我们发现了 “变量 常量+变量” 这样的性质,而我们可以这样分析它为:

「未知量」=「关于 k 的变量」 「常量 」+「关于 k 的另一个变量 」。

那么两个变量都和 k 有关,我们可以将其描述为二元组 。那么这个二元组有什么用呢?我们可以将方程式理解为一个一次函数:

是已知常量 是关于 已知变量 未知量。二元组 就变成了决策点

因此我们的问题变成了:

给定 和坐标系中若干个点 ,要求我们最小化 ,也就是求最小截距。

斜率优化

到上面为止,我们添油加醋地抽象出了一次函数的模型。利用这样一个模型,我们开始斜率优化

两个决策之间的关系

我们考虑两个决策点 ,如果 更优,那么显然

可以看出 是直线 PQ 的斜率,记为 。因此我们有这样的引理

引理 1 对于两个决策点 ,如果 ,那么 P 比 Q 更优,反之亦然。

决策的单调性

由引理 1,我们可以推导出以下的引理

引理 2 对于三个决策点 ,如果 ,那么 Q 不可能成为最优决策。

证明:

  • 如果 ,那么 优于 优于
  • 如果 ,那么 优于 优于 ,最优决策在 或者 中产生;
  • 如果 ,那么 优于 优于

由引理 2,我们考虑从小到大枚举 ,维护一个斜率递减的决策二元组序列

决策点的环境变化

尽管我们已经想到了维护单调的决策队列,但在这之前我们要确认决策的出现顺序与决策集合的变化

  • i 是从 枚举到 的,这意味着 单调递减
  • 是从 枚举到 的,这意味着 单调递增
  • 随着 i 变成 的取值集合从 变成了 ,即增加了决策点 .
  • 因此,只要我们保证 不变,那么上述决策集合可以在均摊 的时间内完成转移

整体算法

于是,我们将 放在最外层循环,在里面维护一个从队首到队尾斜率递减,横坐标 x 递增的决策二元组队列。

因为 是单增的,意味着我们每次会向队列的末尾添加新的决策点 . 在插入的过程中要根据引理 2来维护上凸壳的性质不变。

因为 是单减的,根据引理 1,意味着我们每次需要排除队首不满足 的决策,然后再用当前队首的决策更新当前的未知量。

代码

#include<cstdio>
#include<algorithm>
#define int long long
using namespace std;
const int N=1e5+5,K=210;
signed n,k,p[N][K],q[N],l,r;
int s[N],ff[N],gg[N],*f,*g;// 滚存优化

double slope(int a,int b){// 两个决策点的斜率
    return s[a]==s[b]?1e18:(g[a]-s[a]*s[a]-g[b]+s[b]*s[b])*1.0/(s[a]-s[b]);
}
signed main(){
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)scanf("%d",&s[i]),s[i]+=s[i-1];
    f=ff,g=gg;
    for(int j=1;j<=k;j++){
        l=r=1,q[r]=0;
        for(int i=1;i<=n;i++){
            while(l<r&&slope(q[l],q[l+1])>=-s[i])++l;// 队首出队
            f[i]=g[q[l]]+s[q[l]]*(s[i]-s[q[l]]),p[i][j]=q[l];// 记录当前最优解
            while(l<r&&slope(q[r-1],q[r])<=slope(q[r],i))--r;// 维护凸壳
            q[++r]=i;
        }
        swap(f,g);
    }
    printf("%lld\n",g[n]);
    signed cur=p[n][k];
    while(k)printf("%d",cur),cur=p[cur][--k];// 输出方案
    return 0;
}

HNOI2008 玩具装箱

给一个整数序列 和整数 ,把 放入一个容器的代价为

不关心容器的个数,问把所有数放进容器的最小代价。

分析

既然不关心个数,那么

表示放前 i 个数的最小代价

定义 .(前缀和)

那么化一下式子

抽象一下模型

同样的, 是常量, 是关于 的变量, 未知量

坐标系的点对应如下:

那么决策 优于 的条件为:

那么对于 $P(x,y),Q(x_1,y_1),R(x_2,y_2),xK(Q,R) Q$ 不会成为最优决策。

于是维护一个下凸壳即可,每次增加的决策点是

代码

#include<cstdio>
#define int long long
using namespace std;
const int N=5e4+5;
int n,L,s[N],q[N],l,r,f[N];
int sqr(int x){return x*x;}
double slope(int x,int y){
    return (sqr(s[x-1]+x)+f[x-1]-sqr(s[y-1]+y)-f[y-1])*1.0/(s[x-1]+x-s[y-1]-y);
}
signed main(){
    scanf("%lld%lld",&n,&L);
    for(int i=1;i<=n;i++)scanf("%lld",&s[i]),s[i]+=s[i-1];
    l=1,r=0,f[0]=0;
    for(int i=1;i<=n;i++){
        // 添加决策 j=i
        const int m=i+s[i]-L;
        while(l<r&&slope(q[r-1],q[r])>=slope(q[r],i))--r;
        q[++r]=i;
        while(l<r&&slope(q[l],q[l+1])<=2*m)++l;// 排除队首无用决策
        const int j=q[l],x=s[j-1]+j;
        f[i]=-2*m*x+x*x+f[j-1]+m*m;
    }
    printf("%lld",f[n]);
    return 0;
}

[APIO2010] 特别行动队

给三个整数 表示一个函数 .

给一个整数序列 ,并且合并 成一组的代价为 .

不考虑组数,问把所有数合并成若干组的最大代价。

分析

方程如下

化简

探求最优条件

代码

这里给出一个斜率优化模板代码,可读性较强,适合初学者使用

#include<cstdio>
#define int long long
using namespace std;
const int N=1e6+6;
int n,a,b,c;
int s[N],l,r,q[N],f[N];

int X(int j){return s[j];}
int Y(int j){return a*s[j]*s[j]-b*s[j]+f[j];}
int T(int i){return a*s[i]*s[i]+b*s[i]+c;}
int M(int i){return -2*a*s[i];}

double slope(int x,int y){return (Y(x)-Y(y))*1.0/(X(x)-X(y));}

signed main(){
    scanf("%lld%lld%lld%lld",&n,&a,&b,&c);
    for(int i=1;i<=n;i++)scanf("%lld",&s[i]),s[i]+=s[i-1];
    l=1,r=0;
    for(int i=1;i<=n;i++){
        // 添加决策 i-1.
        while(l<r&&slope(q[r-1],q[r])<=slope(q[r],i-1))--r;
        q[++r]=i-1;
        while(l<r&&slope(q[l],q[l+1])>=-M(i))++l;
        f[i]=M(i)*X(q[l])+Y(q[l])+T(i);//b=mx+y+T
    }
    printf("%lld",f[n]);
    return 0;
}

Usaco2008 Mar 土地购买

N 个矩形 。定义估价函数 f(S)

求将 N 个矩形任意分组后的最小估价,

估价函数的含义即为,集合中的最大的长和最大的宽的积。

首先,对于两个矩形 ,如果 ,显然可以把 包在 ​中,那么可以删掉 而不影响估价。于是把矩形按 排序。可以根据 的关系删除,最后可以得到一个 单增 单减的序列。

考虑求这个序列的最小估价。当选定一个 作为最大的宽时,显然 的矩形的宽都小于等于 ;选定一个 作为最大的长时, 的矩形的长都小于等于 。于是限定 ,这时 的矩形就是能够包含在内的矩形,其他矩形都不满足。不妨贪心地全部选择。也就是说,我们按连续的一段划分分组。

设 f[i] 表示前 i 个的最小估价

斜率优化 DP 即可, .

贪心地连续选择为什么是对的?口糊:反正都是合法的,选总比不选好。

阶段小结

回顾三道例题的 DP 方程:

最后他们分别被化为了

抽象出的数学模型归纳为

其中 未知量 关于已知量的常量 关于已知量的变量。那么我们根据题目要求,判断是维护上凸壳(最大值)还是下凸壳(最小值),并更新 DP 值即可。

关于非单调的扩展

决策点非单调

如果决策点的横坐标 不单调,那么如何维护凸壳?

这个时候,有可能会在中间插入一个决策 ,那么我们在决策点序列上二分,找到两个相邻的点 ,使得

然后用 结合引理 2 把 P 两边不需要的决策删掉,维护凸壳性质,再插入 P 决策即可,可采用平衡树维护凸壳序列。

斜率非单调

如果斜率 非单调呢?

这个时候就需要我们维护整个凸壳,每次找最优解的时候在凸壳上二分,找到一个决策点 使得 (下凸壳)

或者 (上凸壳),则决策 就是当前未知量的最优决策。

这个过程要加一个 的复杂度。

SDOI2012 任务安排

N 个任务标号 1 到 N。第 i 个任务单独完成所需的时间是 。有一台机器可以分批处理任务,每批包含相邻的若干任务。处理一批任务时

  1. 处理前的启动时间为 S
  2. 处理这批任务所需的时间是各个任务需要时间的总和
  3. 同一批任务将在同一时刻完成
  4. 每个任务的费用是它的完成时刻乘以一个费用系数

确定一个分组方案,使得总费用最小。

题目的代价种类繁多,影响代价的因素有 ,分组数量,分组方案。显然 是题目给定。那么能否设计一个状态尽量少的 DP 呢?可以尝试不考虑分组数量。

定义 表示将前 i 个分组处理的最小代价。

定义 (一个前缀和,一个后缀和)。

考虑最优决策, .(即 ,决策 的后面(相当于添加一个决策

注意到斜率 并不是单调的,不过决策序 是单调的,因此可以简单维护一个下凸壳,查询的时侯在凸壳上二分即可。

#include<cstdio>
#define int long long
using namespace std;
const int N=3e5+5;
int n,s;
int T[N],F[N];
int f[N];

int Y(int j){return s*F[j+1]+f[j]-T[j]*F[j+1];}
int M(int i){return T[i];}
int X(int j){return F[j+1];}

int slope(int i,int j){return (Y(i)-Y(j))*1.0/(X(i)-X(j));}// 算斜率

int q[N],lq;
int find(int k){// 二分查找最优决策,k: 斜率
    if(lq==0)return -1;// 没有
    int l=1,r=lq;
    while(l<r){int mid=(l+r)>>1;
        double kmid=mid==lq?1e99:slope(q[mid],q[mid+1]);//BUG#2: 没有套 q
        if(-k>=kmid)r=mid;//BUG#1:k 没加负号
        else l=mid+1;
    }
    return q[l];
}
void add(int j){// 添加一个决策到凸壳中
    while(lq>=2&&slope(j,q[lq])>slope(q[lq],q[lq-1]))--lq;
    q[++lq]=j;
}

signed main(){scanf("%lld%lld",&n,&s);
    for(int i=1;i<=n;i++)scanf("%lld%lld",&T[i],&F[i]);
    for(int i=1;i<=n;i++)T[i]+=T[i-1];// 前缀和
    for(int i=n-1;i>=1;i--)F[i]+=F[i+1];// 后缀和

    for(int i=0;i<=n;i++){int j=find(M(i));// 寻找最优决策
        if(j!=-1)f[i]=M(i)*X(j)+Y(j);// 找到最优决策就更新
        add(i);// 添加决策 i
    }
    printf("%lld\n",f[n]);
    return 0;
}

  转载请注明: Sshwy's Blog 斜率优化 DP 入门

 上一篇
[HAOI2011]Problem A [HAOI2011]Problem A
题意一次考试共有 个人参加,第 个人说:“有 个人分数比我高, 个人分数比我低。” 问最少有几个人没有说真话(可能有相同的分数) . 分
2019.01.16
下一篇 
[USACO12MAR] 花盆 [USACO12MAR] 花盆
题意给定 n 个点 和一个整数 ,求一个最小区间 ,使得点集 中的纵坐标的极差 最大. 输出区间长度 . $n\leq 10^5,x
2019.01.15
  目录