Processing math: 0%

浅谈斜率优化——截距优化

浅谈斜率优化——截距优化

最近(两个月前)学习了斜率优化 —— 一种优化 1D1D 动态规划转移方程的高效方法,在较高难度的比赛中是一种十分常见的 DP 优化手段。鉴于我之前(一年前)也稍微接触过一点相关方面的知识,但是完全没有搞懂(太菜了),最近(两个月前)再配合 orzCJK学长 提出的截距优化的思想理念才对于斜率优化问题有了深刻的见解,故在这里对 orzCJK学长 的 斜率优化_截距优化!.pdf 进行详细的解释说明。

 

首先,1D1D 指的是状态数 O(n) 转移 O(n) 的动态规划方程。在满足一些条件的情况下,斜率优化可以将转移的 O(n) 优化至 O(logn) 甚至可以到 O(1) 。这样时间复杂度就由 O(n^2) 变为 O(nlogn) 甚至是 O(n) ,可见斜率优化的高效性。

如果有一个 DP 方程的某个状态为 f_i ,如果能推导出类似于 f_i=c_i + \min\limits_{j<i \land \cdots}{\{a_j + w_i \cdot b_j\}} ,那么这个转移方程就可以使用斜率优化进行优化。

然而普通的转移方程并没有什么特殊的地方,使用经典的方法(我也不会)略显繁琐,所以现在我们要赋予它以几何意义。(时刻注意,这个转移方程的意义是对于一个 ij < i 范围内寻找 j 使 a_j + w_i \cdot b_j)最小。)

换一下变量名,设 y_j=a_j, k_i=-w_i, x_j=b_j ,那么这样需要最小化的式子就变为 \underbrace{a_j}_{y_j} – \underbrace{-w_i}_{k_i} \cdot \underbrace{b_j}_{x_j} 。这不就是截距 b = y – kx 吗?!!也就是说,要最小化的就是一条\left(x_j, y_j\right)斜率为 k_i 的直线的截距

换句话说,把所有对于当前 i 可转移的 j 都表示为二维平面上的一个点 p_j=\left(x_j, y_j\right) ,我们需要做的就是在所有这样的点中,找到一个点,使经过它且斜率为 k_i 的直线的截距最小!这也是为什么斜率优化就是截距优化的原因,它其实优化的是截距!

现在想象一条斜率固定的直线从下往上平移,当它第一次经过某个点 p_j 时,这时的截距肯定取到最小值。那么这个点 p_j 在什么地方呢?显然,它会在所有 p 组成的下凸壳上。

那么现在只要维护这个下凸壳,每次在上面找点使得截距最小,拿来更新 …

YZOJ P3840 [2018省队集训]序列

YZOJ P3840 [2018省队集训]序列

时间限制:2000MS      内存限制:524288KB

难度: 8.0

  • 题目描述

给定一个长度为 n 的序列 x

你需要从序列中选出一些位置。对于i位置,如果它被选中,你会获得 x_i 的收益;否则找到最小的 j 使得第 j 个位置到第 i 个位置都没有被选中,你需要付出 i-j+1 的代价。

此外,你选出的位置必须满足 x_i单调不下降的。

最大化收益减去代价的结果。

  • 输入格式

第一行一个正整数 n,第二行 n 个整数 x_1 ~ x_n

  • 输出格式

输出一行一个整数表示答案。

  • 样例 1 输入

  • 样例 1 输出

  • 样例 1 说明

选择第 1, 3, 5, 7 个位置,获得收益 1+2+3+4=10 ,第 2, 4, 6 个位置的代价分别为 1, 1, 1 ,收益减去代价为 10-3=7

  • 样例 2 输入

  • 样例 2 输出

  • 数据规模与约定

对于 5\% 的数据, 1 \leq n \leq 5 。…

[CEOI2017]Building Bridges

[CEOI2017]Building Bridges

时间限制:1000MS      内存限制:131072KB

难度: 7.2

  • 题目描述

n 根柱子依次排列,每根柱子都有一个高度。第 i 根柱子的高度为 h_i

现在想要建造若干座桥,如果一座桥架在第 i 根柱子和第 j 根柱子之间,那么需要 (h_i-h_j)^2 的代价。
在造桥前,所有用不到的柱子都会被拆除,因为他们会干扰造桥进程。第 i 根柱子被拆除的代价为 w_i​,注意 w_i 不一定非负,因为可能政府希望拆除某些柱子。

现在政府想要知道,通过桥梁把第 1 根柱子和第 n 根柱子连接的最小代价。注意桥梁不能在端点以外的任何地方相交。

  • 输入格式

第一行一个正整数 n

第二行 n 个空格隔开的整数,依次表示 h_1, h_2, \cdots, h_n

第三行 n 个空格隔开的整数,依次表示 w_1, w_2, \cdots, w_n

  • 输出格式

输出一行一个整数表示最小代价,注意最小代价不一定是正数。

  • 样例输入

  • 样例输出

  • 数据范围与提示

对于 30\% 的数据,有 1 \leq n \leq 1000

对于另外 40\% 的数据,有 \left| w_i \right| \leq 20 ,保证存在一种最优方案,除了头尾两根柱子外,最多只保留两根柱子;

对于 100\% 的数据,有 2 \leq n \leq 10^50 \leq h_i,\left| w_i\right| \leq 10^6

数据来源 LOJ 2483

 

 

已搬至 YZOJ P4254 。…

[SDOI2012]任务安排

[SDOI2012]任务安排

时间限制:1000MS      内存限制:131072KB

难度: 7.1

  • 题目描述

按顺序给定 N 个子任务,每个任务用时 t_i ,费用系数 f_i

可以把连续的若干个(或一个)子任务合成为一个大任务,大任务的用时和费用系数分别为其中每个子任务的用时之与费用系数之。开始一个大任务之前需要准备时间 S,一个大任务的费用为他的 完成时刻 \times 费用系数 ,问按顺序执行完所有的大任务后,最小的费用和为多少。

形式化的,将 N 个任务划分成若干个块,每一组任务 M_i 花费代价 (T+\sum{t_j}+S) \times \sum{f_j}j \in M_iT 为执行到这个任务之前花费的时间,求执行完所有任务的最小代价和。

  • 输入格式

第一行一个整数 N

而后 N 行中,第 i 行包含一个可能为负的整数 t_i 和一个非负整数 f_i

  • 输出格式

一个整数,表示最小的代价和。

  • 样例输入

  • 样例输出

  • 样例说明

如果分组方案是 \{1,2\}\{3\}\{4,5\},则完成时间分别为 \{5,5,10,14,14\},费用 C=\{15,10,30,42,56\},总费用就是 153

  • 数据规模与约定

对于 20\% 的数据,1 \leq N \leq 1000

对于另外 40\% 的数据, 1 \leq N \leq 300000

对于前 60\% 的数据,0 \leq t_i \leq 2^8

对于后 40\% 的数据,1 \leq N \leq 100000-2^8 \leq t_i \leq 2^8

对于 100\% 的数据, \(0 \leq S, f_i …

YZOJ P2021 [APIO2014]sequence

YZOJ P2021 [APIO2014]sequence

时间限制:2000MS      内存限制:131072KB

难度: 5.7

  • 题目描述

给定一个长度为 N 的非负整数序列 a ,现要把它分割成 k+1 个连续非空的子序列。

每次分割可以选择一段剩余长度超过 1 的序列,并在其中选择一个位置,把它分割成两个连续非空的子序列。这样做可以得到一些 Bonus,为分割出的两个新序列中元素和乘积

现要找到一种方案,使得经过 k 次分割后,能得到的 Bonus 最多。

  • 输入格式

第一行包含两个整数 n,  k

第二行包含 n 个非负整数,表示序列 a

  • 输出格式

第一行包含一个整数,为最大 Bonus

第二行包含 k1n-1 的整数,表示最优方案。其中第 i 个数 x_i 表示在该方案中,进行第 i 次操作时,应该选择第 x_i 个数后面的位置,并将这个数所在的序列分成两部分。

如果有多个最优方案,输出其中任意一种即可。

  • 样例输入

  • 样例输出

  • 数据规模与约定

数据满足 2 \leq n \leq 1000001 \leq k \leq min\{n-1,200\}

 

 

 …

YZOJ P3669 [USACO2008 Mar]土地购买

YZOJ P3669 [USACO2008 Mar]土地购买

时间限制:1000MS 内存限制:262144KB

难度:6.0 (自评)

  • 题目描述

农夫 John 准备扩大他的农场,他正在考虑 N1 \leq N \leq 1,000,000) 块长方形的土地。

每块土地的长宽满足 (1 \leq\leq 1,000,0001 \leq\leq 1,000,000)。每块土地的价格是它的面积,但 FJ 可以同时购买多块土地。

这些土地的价格是它们最大的长乘以它们最大的宽,但是土地的长宽不能交换。如果 FJ 买一块 3 \times 5 的地和一块 5 \times 3 的地,则他需要付 5 \times 5=25

FJ 希望买下所有的土地,但是他发现分组来买这些土地可以节省经费。他需要你帮助他求出最小的经费。

  • 输入格式

输入文件的第 1 行一个数 N, 表示土地块数。第 2 行至第 N+1 行,每行包含两个数,表示第 i 块土地的长和宽。

  • 输出格式

最小的可行费用。

  • 样例输入

  • 样例输出

 

 

 …