首页 > 其他分享 >斜率优化学习笔记

斜率优化学习笔记

时间:2023-08-06 21:44:40浏览次数:30  
标签:直线 int 决策 笔记 凸包 斜率 优化 first

这是等了好久的笔记了。

斜率优化一直是我 OI 中的一个大坑,我刚接触它的时候是在 摆渡车 这题,看到斜率凸包啥的,那时候我才是六年级,十分的不理解,于是一直觉得它十分困难。

暑假终于迎来了转机,NLFS 讲 DP 优化那天顺便讲了下斜率优化,终于大悟,乃写此文章,供复习等用。

先来看一道题:

斜率优化的板子题

给你 $n$ 个点,多次询问,每次给你一个斜率 $k$,需要在这 $n$ 个点中选出一个点 $(x,y)$,使得 $kx+y$ 最大。

斜率优化主要是推式子,我们来看如果有两个点 $(x_1,y_1)$ 和 $(x_2,y_2)$,对于同一个 $k$,什么时候 $1$ 比 $2$ 更好呢?

将式子代入可得 $kx_1+y_1>kx_2+y_2$,移项并提取公因式可得 $k(x_1-x_2)>y_2-y_1$,此时我们不妨设 $x_1>x_2$,则两边同时除以正数,不等号方向不变,得到 $k>\frac{y_2-y_1}{x_1-x_2}$。

两边同时乘以 $-1$ 可得 $-k<\frac{y_1-y_2}{x_1-x_2}$,输入 $k$ 时可将其取反,这个不重要,最终得到 $k<\frac{y_1-y_2}{x_1-x_2}$,我们看这个是什么,这不就是经过点 $(x_1,y_1)$ $(x_2,y_2)$ 的直线的斜率吗?

所以,总结如下:当 $(x_1,y_1)$ 优于 $(x_2,y_2)$ 时,则联结这两点所得的直线斜率大于 $k$。

接着我就要谈大家最不耐烦也是最难听懂的部分,凸包,我尽量说的详细一些。

先来考虑最简单的三个点 $x_1$ $x_3$ $x_3$ 的情况,这是一种:

 

此时显然可以发现 $k_1<k_2$,如果要统计 $x_2$ 的答案,此时一定有 $k_1>k$,然而 $k_2>k_1$,所以 $k_2>k$,即 $x_3$ 比 $x_2$ 优,所以 $x_3$ 最优,此时呈下凸壳,我们发现下凸壳的所有点除了最后的那个点都不会被统计答案,所以下凸壳是没有任何的意义的。

那么上凸壳呢?

 

此时 $k_1<k_2$,如果要统计 $x_2$ 的答案,此时也一定有 $k_1>k$,但是 $k_2<k_1$,不一定有 $k_2>k$,所以 $x_2$ 有可能被统计,上凸壳是有意义的。

现在,我们对于每条直线找到它的最优决策点,首先要求得这些点的凸包,如果你不会请前往 【模板】二维凸包。

如图:

 

可以发现,当一条直线经过凸包上的一个点,且不碰到凸包,那么这个点就是这条直线的最优决策点,用眼瞪一下可得:

经过两点 $x_2,x_1$ 的直线斜率大于 $k$,所以 $x_2$ 优于 $x_1$。

也能得到 $x_3$ 和 $x_2$ 这两点的连线斜率小于 $k$,刚刚的结论反一下可得 $x_3$ 劣于 $x_2$。

同理可得所有的点在 $k_1$ 下都是劣于 $x_2$ 的,所以 $x_2$ 是 $k_1$ 的最佳决策点。

得到了这个结论后我们来看如何得到所有直线的最佳决策点。

1.离线做法

对于直线 $k_1$,$k_2$,在刚刚的那个图中的决策点为 $x_2,x_3$,则一定有 两点 $x_3,x_2$ 所连得的直线斜率小于 $k1$,大于 $k2$,于是可得 $k_1>k_2$。

进一步推广可知:对于两个直线 $k_1,k_2$,若 $k_1$ 的决策点在 $k_2$ 前,则 $k_1$ 的斜率大于 $k_2$。

反过来一下得到斜率越大的直线决策点在越前面。

于是可以将斜率从大到小排序,每一轮取出当前斜率最大的直线放在后面的点上试答案(即看下能不能碰到凸包),如果不是最有决策点,那么对于后面斜率更小的直线,这个点也一定不是它的最优决策点。

剩下的直线决策点都是最后一个点了。

然后判断是否是最优答案其实只需要判这个点的答案是否比两边的答案都要大即可。

看一下代码吧:

 

#include <iostream>
#include <algorithm>
#define int long long
using namespace std;
int n, m, tp;
int ans[100005];
pair <int, int> a[100005], tb[100005];
struct Line {int k;int id;}q[100005];
bool cmp (Line l1, Line l2) {return l1.k > l2.k;}
int k (pair <int, int> p1, pair <int, int> p2) {return (p1.second - p2.second) / (p1.first - p2.first);}
int fun (pair <int, int> p, int k) {return -p.first * k + p.second;}
signed main () {
    cin >> n >> m;
    for (int i = 1; i <= n; i ++) cin >> a[i].first >> a[i].second;
    sort (a + 1, a + n + 1);
    for (int i = 1; i <= n; i ++) {
        while (tp >= 2) {
            if ( (tb[tp].second - tb[tp - 1].second) * (a[i].first - tb[tp].first) <= (a[i].second - tb[tp].second) * (tb[tp].first - tb[tp - 1].first) ) tp --;
            else break;
        }
        tb[++ tp] = make_pair (a[i].first, a[i].second);
    }
    for (int i = 1; i <= m; i ++) {
        cin >> q[i].k;
        q[i].k = -q[i].k;
        q[i].id = i;
    }
    sort (q + 1, q + m + 1, cmp);
    int r = 1;
    for (int i = 1; i <= m; i ++) {
        if (r == tp) {
            ans[q[i].id] = fun (tb[r], q[i].k);
            continue;
        }
        while (r != tp && fun (tb[r], q[i].k) <= fun (tb[r + 1], q[i].k) ) ++ r;
        ans[q[i].id] = fun (tb[r], q[i].k);
    }
    for (int i = 1; i <= m; i ++) cout << ans[i] << "\n";
    return 0;
}

 2.在线二分做法

其实大家有没有发现,若点 $x_2$ 是 $k_1$ 的最优决策点,$x_2$ 两端的点是 $x_1$ 和 $x_3$,则 $x_1$ $x_2$ 的斜率必然大于 $k_1$,$x_2$ $x_3$ 的斜率必然小于 $k_1$,凸包上的点斜率是递减的,所以二分即可。

代码不补了。

例题二咕咕咕

标签:直线,int,决策,笔记,凸包,斜率,优化,first
From: https://www.cnblogs.com/Xy-top/p/17610117.html

相关文章

  • tarjan,点双和边双学习笔记。
    发现之前学的真的一塌糊涂呢(/ω\)很多非常精髓的地方理解的都不够好,比如说为啥我要用一棵dfs树来为框架,跑tarjan?这里我就理解的不好,所以我来重新写一篇,加深加深印象。以下一切默认为无向图。0.基本概念这里面说的非常不严谨,只是为了方便理解啦awa连通分量:你可以简单的......
  • Dijkstra最短路径算法及其优化
    Dijkstra最短路径算法及其优化图示过程可以参考图文详解Dijkstra最短路径算法(freecodecamp.org)直接给出Java版本的普通实现方式:/***最普通的实现形式,时间复杂度是O(n2),空间复杂度是O(n)*@paramweight*@paramstart*@return*/publicstaticint[]getDij......
  • 二次剩余学习笔记
    注意,下面的运算都是在模意义下进行的。给定\(n\),求\(x^2\equivn\)\(x\)存在条件为\(n^{\frac{p-1}2}=1\),证明用费马小定理,略。如何求出\(x\),随机一个不存在二次剩余的值\(a^2-n\),设为\(w^2\)这里可以把\(w\)理解为一个虚数。由于\(w^2\)不存在二次剩余,所以\[w......
  • 【学习笔记】类欧几里得算法
    概述主要是求以下三个式子:\[f(a,b,c,n)=\sum_{i=0}^n\left\lfloor\dfrac{ai+b}{c}\right\rfloor\]\[g(a,b,c,n)=\sum_{i=0}^ni\left\lfloor\dfrac{ai+b}{c}\right\rfloor\]\[h(a,b,c,n)=\sum_{i=0}^n\left\lfloor\dfrac{ai+b}{c}\right\rfloor^2\]求\(f......
  • GAMES101笔记(03)
    前几个月忙着拯救地球所以有比较长时间的空档这次笔记对应的是games101内容的第六课,至于为什么跳过第五课因为第五课我感觉也没啥需要记笔记的,基本就是光栅化的一些基本概念以及最基本的一些实现理念,视频最后讲到了关于锯齿和走样的一些东西,第六课开头即紧接着这部分进行讲解采......
  • Vue学习笔记:路由开发 Part 02
    在上一篇中,默认情况下浏览器控制台会提示 [VueRouterwarn]:Nomatchfoundforlocationwithpath"/"这是因为没有定义path为/的情况导致的。在实际使用中,可以将/通过路由进行绑定,也可以通过重定向,进行跳转。路由重定向为/,通过redirect进行重定向import{createRouter,crea......
  • 「学习笔记」二维数点
    P2163[SHOI2007]园丁的烦恼-洛谷|计算机科学教育新生态(luogu.com.cn)这个是二维数点的板子题,二维数点这一类题目就是上面的题所描述的,我们用树状数组+离散化来解决这个问题。这里就不解释了,记录此篇博文的目的主要就是提醒自己曾经学过这个,看看代码,方便回忆起来。这......
  • 一篇不错的优化的文章
    刷到大佬的文章浅论OI中的卡常技巧(基本完成)-知乎(zhihu.com)对其中一些东西问了AI,存一下有关bitset有关if-else和switch-case位运算要加括号保险。 不要无脑inline和register 循环的顺序并发计算与循环展开不要默认开defineintlonglong ......
  • 【狂神说Java】Java零基础学习笔记-Java方法
    【狂神说Java】Java零基础学习笔记-Java方法Java方法01:何谓方法?System.out.println(),那么它是什么呢?Java方法是语句的集合,它们在一起执行一个功能。方法是解决一类问题的步骤的有序组合方法包含于类或对象中方法在程序中被创建,在其他地方被引用设计方法的原则:方......
  • 博弈论笔记
    博弈论公平组合游戏公平组合游戏(ImpartialGame)的定义如下:\(\bullet\)游戏有两个人参与,二者轮流做出决策,双方均知道游戏的完整信息;\(\bullet\)任意一个游戏者在某一确定状态可以作出的决策集合只与当前的状态有关,而与游戏者无关;\(\bullet\)游戏中的同一个状态不可能多次......