- Java锁的逻辑(结合对象头和ObjectMonitor)
- 还在用饼状图?来瞧瞧这些炫酷的百分比可视化新图形(附代码实现)⛵
- 自动注册实体类到EntityFrameworkCore上下文,并适配ABP及ABPVNext
- 基于Sklearn机器学习代码实战
对于像如下这样的 dp 方程,我们可以使用斜率优化解决.
例题: P2900 Land Acquisition G 。
显然,如果 \(w_i \ge w_j\) 且 \(l_i \ge l_j\) ,那么土地 \(j\) 可以直接被土地 \(i\) 并购.
考虑将所有土地按 \(w_i\) 降序排序, \(w_i\) 相同的按 \(l_i\) 降序排序,再通过双指针保留不能被其它土地并购的土地.
注意到此时被保留下的土地, \(w_i\) 满足 单调递减 , \(l_i\) 满足 单调递增 .
令 \(dp_i\) 表示将第 \(1 \sim i\) 块土地并购的最小代价,不难列出 dp 方程:
上面的方程复杂度为 \(O(n^2)\) ,然而 \(n \leq 5 \times 10^4\) ,我们需要想办法优化.
先将 \(\min\) 去掉,再把 \(w_{j + 1} \times l_{i}\) 移到左边,得:
将所有能够转移到 \(i\) 的 \(j\) 视为一个点 \((-w_{j + 1}, dp_j)\) ,那么问题就转化成了:
上面这句话有点抽象,不妨将 原方程 与 一次函数 做一个对比,发现它们确实十分相似:
本质就是我们拿着一条斜率为 \(l_i\) 的直线,从下往上靠(增加它的截距),直到某一时刻这条线经过了我们维护的一个或多个点,停下来,此时截距( \(dp_i\) )一定是最小的.
仔细观察可以发现,无论斜率 ( \(l_i\) ) 是多少,有些点一定不会被第一次经过(如下图灰色点)。将这些点去除,剩余的点恰好形成了一个右下凸壳:
不妨先来维护这个凸壳,假设现在加入点 \(C(-w_{i + 1}, dp_i)\) ,考虑凸壳上最新的两个点 \(A\) 和 \(B\) ,只可能有以下两种情况:
记点 \(X\) 与点 \(Y\) 所连成的直线斜率为 \(\text{slope}(X, Y)\) ,则 \(C\) 能直接加入凸壳当且仅当 \(\text{slope}(A, B) \leq \text{slope}(B, C)\) .
这时候一定有 \(\text{slope}(A, B) \geq \text{slope}(B, C)\) ,故需要将 \(B\) 弹出凸壳,在拿剩余凸壳最新的两个点与 \(C\) 作比较.
由于这些点的 \(x\) 单调递增,可以使用类似单调栈的方法维护,时间复杂度 \(O(n)\) .
接下来就是要在维护出的凸壳上找到最优决策点,随便画一张图,由于这些直线的斜率一定不断增加,所以最优决策点一定不断向凸壳上方移动:
进一步观察,可以发现,如果凸壳上相邻的两点 \(A\) 和 \(B\) 满足 \(\text{slope}(A, B) \leq l_i\) ,那么点 \(B\) 永远在 \(i\) 以后一定 不会成为最优决策点。不妨把原来维护凸壳的单调栈换成单调队列,通过凸壳最前面两点的斜率判断是否弹出队头。最终,队头一定是当前的最优决策点.
时间复杂度 \(O(n)\) (本题由于要排序所以总复杂度应该为 \(O(n \log n)\) ,这里只计算了 dp 的复杂度)。代码如下:
#include <bits/stdc++.h>
using namespace std;
int n, pos, q[50005], h, t;
long long dp[50005];
struct land
{
int w, l;
bool operator<(const land t) const
{
return w == t.w ? l > t.l : w > t.w;
}
} p[50005];
double X(int j)
{
return -p[j + 1].w;
}
double Y(int j)
{
return dp[j];
}
double slope(int x, int y)
{
return (Y(x) - Y(y)) / (X(x) - X(y));
}
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d%d", &p[i].w, &p[i].l);
sort(p + 1, p + n + 1);
for (int i = 1; i <= n; i++)
if (p[i].l > p[pos].l)
p[++pos] = p[i];
for (int i = 1; i <= pos; i++)
{
while (h < t && slope(q[h], q[h + 1]) <= p[i].l)
h++;
dp[i] = dp[q[h]] + p[q[h] + 1].w * 1LL * p[i].l;
while (h < t && slope(q[t - 1], q[t]) >= slope(q[t], i))
t--;
q[++t] = i;
}
printf("%lld", dp[pos]);
return 0;
}
例题: P3195 玩具装箱 。
记 \(s_i = \sum_{j=1}^i C_i\) ,则可以列出 dp 方程:
令 \(a_i = s_i + i - 1 - L, b_i = s_j + j\) ,原方程变为 。
即 。
将 \(\min\) 及其以外得东西去掉,得 。
化为直线的形式 。
类似与之前的形式,把每个 \(j\) 视作点 \((b_j, dp_j + b_j^2)\) ,每次直线的斜率为 \(2a_i\) ,做斜率优化即可.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, L, C, h, t, q[50005];
ll s[50005], dp[50005];
double X(int j)
{
return s[j] + j;
}
double Y(int j)
{
return (s[j] + j) * (s[j] + j) + dp[j];
}
double slope(int i, int j)
{
return (Y(i) - Y(j)) / (X(i) - X(j));
}
int main()
{
scanf("%d%d", &n, &L);
for (int i = 1; i <= n; i++)
{
scanf("%d", &C);
s[i] = s[i - 1] + C;
}
h = t = 1;
for (int i = 1; i <= n; i++)
{
while (h < t && slope(q[h], q[h + 1]) <= 2 * (s[i] + i - L - 1))
h++;
dp[i] = dp[q[h]] + sq(s[i] - s[q[h]] + i - q[h] - 1 - L);
while (h < t && slope(q[t - 1], q[t]) >= slope(q[t], i))
t--;
q[++t] = i;
}
printf("%lld", dp[n]);
return 0;
}
例题: P5785 任务安排 (弱化版 P2365 任务安排 ) 。
至于方程是如何提前计算贡献的我就不细说了,记 \(\text{sumT}_i = \sum_{j=1}^i T_i,\text{sumC}_i = \sum_{j=1}^i C_i\) ,可列出方程:
展开整理成直线形式,即 。
每个 \(j\) 所代表的点: \((\text{sumC}_i, dp_j)\) ,直线斜率 \(\text{sumT}_i + s\) .
正准备敲板子的你突然发现了这一条限制:
也就是说 。
那么 \(\text{sumT}_i + s\) 就不单调了,就不能一味地弹出队头了! 。
可凸壳上相邻两点地斜率还是单调的啊!那么只需要在凸壳上二分,找决策点即可.
时间复杂度 \(O(n \log n)\) .
#include <bits/stdc++.h>
using namespace std;
long long n, s, sumT[300005], sumC[300005], dp[300005], top, stk[300005];
long long X(int j)
{
return sumC[j];
}
long long long Y(int j)
{
return dp[j];
}
int main()
{
scanf("%lld%lld", &n, &s);
for (int i = 1; i <= n; i++)
{
long long t, f;
scanf("%lld%lld", &t, &f);
sumT[i] = sumT[i - 1] + t;
sumC[i] = sumC[i - 1] + f;
}
stk[++top] = 0;
for (int i = 1; i <= n; i++)
{
int l = 1, r = top - 1, pos = stk[top];
while (l <= r)
{
int mid = (l + r) >> 1;
if (Y(stk[mid + 1]) - Y(stk[mid]) > (sumT[i] + s) * (X(stk[mid + 1]) - X(stk[mid])))
pos = stk[mid], r = mid - 1;
else
l = mid + 1;
}
dp[i] = dp[pos] + sumT[i] * (sumC[i] - sumC[pos]) + s * (sumC[n] - sumC[pos]);
while (top > 1 && (Y(stk[top]) - Y(stk[top - 1])) * (X(i) - X(stk[top])) >= (Y(i) - Y(stk[top])) * (X(stk[top]) - X(stk[top - 1])))
top--;
stk[++top] = i;
}
printf("%lld", dp[n]);
return 0;
}
注:斜率优化比较时建议移项,把除法化为乘法;如果使用 double 类型的 slope 很可能会产生精度误差(本题就卡了.
斜率优化小结:
列出方程,先通过一些简单的代换化简成直线形式.
通过 \(\min / \max\) 以及 \(X\) 和 \(Y\) 坐标的单调性判断凸壳方向.
如果直线斜率不单调,使用二分维护.
如果 \(Y\) 坐标不单调,可以证明对最终凸壳没有影响.
如果 \(X\) 坐标不单调,可以考虑 \(\text{CDQ}\) 分治解决,时间复杂度 \(O(n \log^2 n)\) .
最后此篇关于算法学习笔记(3):与斜率优化共舞的文章就讲到这里了,如果你想了解更多关于算法学习笔记(3):与斜率优化共舞的内容请搜索CFSDN的文章或继续浏览相关文章,希望大家以后支持我的博客! 。
OkHttp的作用 OkHttp is an HTTP client。 如果是HTTP的方式想得到数据,就需要我们在页面上输入网址,如果网址没有问题,就有可能返回对应的String字符串,如果这个地址
Record 一个重要的字符串算法,这是第三次复习。 通过总结我认为之所以某个算法总是忘记,是因为大脑始终没有认可这种算法的逻辑(也就是脑回路)。 本篇主要讲解从KMP的应用场景,
SQL 注入基础 【若本文有问题请指正】 有回显 回显正常 基本步骤 1. 判断注入类型 数字型 or 字符型 数字型【示例】:
标签: #Prompt #LLM 创建时间:2023-04-28 17:05:45 链接: 课程(含JupyterNotebook) , 中文版 讲师: An
Swift是供iOS和OS X应用编程的新编程语言,基于C和Objective-C,而却没有C的一些兼容约束。Swift采用了安全的编程模式和添加现代的功能来是的编程更加简单、灵活和有趣。界面则基于
红日靶机(一)笔记 概述 域渗透靶机,可以练习对域渗透的一些知识,主要还是要熟悉 powershell 语法,powershell 往往比 cmd 的命令行更加强大,而很多渗透开源的脚本都是 po
八大绩效域详细解析 18.1 干系人绩效域 跟干系人所有相关的活动. 一、预期目标 ①与干系人建立高效的工作关系 ②干系人认同项目目标 ③支持项目的干系人提高
18.3 开发方法和生命周期绩效域 跟开发方法,项目交付节奏和生命周期相关的活动和职能. 一、预期目标: ①开发方法与项目可交付物相符合; ②将项目交付与干系人价值紧密
18.7 度量绩效域 度量绩效域涉及评估项目绩效和采取应对措施相关的活动和职能度量是评估项目绩效,并采取适当的应对措施,以保持最佳项目绩效的过程。 一、 预期目标: ①对项目状况
pygraphviz 安装,windows系统: 正确的安装姿势: Prebuilt-Binaries/PyGraphviz at master · CristiFati/Prebuilt-Binar
今天给大家介绍IDEA开发工具如何配置devtools热加载工具。 1、devtools原理介绍 spring-boot-devtools是spring为开发者提供的热加载
一 什么是正则表达式 // 正则表达式(regular expression)是一个描述字符模式的对象; // JS定义RegExp类表示正则表达式; // String和RegExp都定义了使用
目前是2022-04-25 23:48:03,此篇博文分享到互联网上估计是1-2个月后的事了,此时的OpenCV3最新版是3.4.16 这里前提是gcc,g++,cmake都需要安装好。 没安装好的,
一、概述 1、Flink 是什么 Apache Flink is a framework and distributed processing engine for stateful comput
一、window 概述 Flink 通常处理流式、无限数据集的计算引擎,窗口是一种把无限流式数据集切割成有限的数据集进行计算。window窗口在Flink中极其重要。 二、window 类型 w
一、触发器(Trigger) 1.1、案例一 利用global window + trigger 计算单词出现三次统计一次(有点像CountWindow) 某台虚拟机或者mac 终端输入:nc -
一、时间语义 在Flink 中涉及到三个重要时间概念:EventTime、IngestionTime、ProcessingTime。 1.1、EventTime EventTime 表示日志事
一、概述 以wordcount为例,为什么每次输入数据,flink都能统计每个单词的总数呢?我们都没有显示保存每个单词的状态值,但是每来一条数据,都能计算单词的总数。事实上,flink在底层维护了每
一、概述 checkpoint机制是Flink可靠性的基石,可以保证Flink集群在某个算子因为某些原因(如 异常退出)出现故障时,能够将整个应用流图的状态恢复到故障之前的某一状态,保 证应用流图状
一、standalone 部署模式 1、下载安装包 下载安装包地址 有两种安装包类型: 第一种是带 Hadoop依赖的(整合YARN) 第二种是不带 Hadoop依赖的(Standalone模式)
我是一名优秀的程序员,十分优秀!