斜率优化入门

前言

斜率优化是一种经典的单调队列优化类型,虽然它的名字很高大上,但是其思想内核非常简单,这篇博客就是用来帮助各位快速入门的

提示:本博客以单调队列的思想理解斜率优化

引入

dp 优化可以怎么分类?

  1. 数据结构维护决策点集的插入与查找

  2. 算法维护决策点集大小,取出无用决策点

而斜率优化 dp 属于第二者,且常常用于优化序列分割问题

Q1

P3195

A1

先列出一个朴素的 dp 方程:

\(dp_i = min(dp_j+(pre[i]+i-pre[j]-j-L-1)^2)\)

然后我们考虑决策点 \(j,k\) 满足 \(k<j\)\(j\) 优于 \(k\)

那么有:

\(dp_j + (pre[i]+i-L-1)^2 + (pre[j]+j)^2 - 2 \times (pre[i]+i-L-1) \times (pre[j]+j) < dp_k + (pre[i]+i-L-1)^2 + (pre[k]+k)^2 - 2 \times (pre[i]+i-L-1) \times (pre[k]+k)\)

\(dp_j + (pre[j]+j)^2 - 2 \times (pre[i]+i-L-1) \times (pre[j]+j) < dp_k + (pre[k]+k)^2 - 2 \times (pre[i]+i-L-1) \times (pre[k]+k)\)

\(dp_j + (pre[j]+j)^2 - dp_k + (pre[k]+k)^2 < 2 \times (pre[i]+i-L-1) \times (pre[j]+j) - 2 \times (pre[i]+i-L-1) \times (pre[k]+k)\)

\(2 \times (pre[i]+i-L-1) \times((pre[j]+j) -(pre[k]+k)) > dp_j + (pre[j]+j)^2 - dp_k + (pre[k]+k)^2\)

然后我们发现这个等式两边全部具有单调性,所以就可以用单调队列维护最优答案

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e6+114;
int sum[maxn],q[maxn];
int dp[maxn];
int n,L;
int top(int j,int k){
	return (sum[j]+j)*(sum[j]+j)+dp[j]-(sum[k]+k)*(sum[k]+k)-dp[k];
}
int down(int j,int k){
	return sum[j]+j-sum[k]-k;
} 
signed main(){
	cin>>n>>L;
	for(int i=1;i<=n;i++) cin>>sum[i];
	sum[0]=dp[0]=0;
	int l=1,r=0;
	q[++r]=0;
	for(int i=1;i<=n;i++) sum[i]+=sum[i-1];
	for(int i=1;i<=n;i++){
		while(l+1<=r&&2*(i+sum[i]-1-L)*down(q[l+1],q[l])>=top(q[l+1],q[l])) l++;
		dp[i]=dp[q[l]]+(i-q[l]-1+sum[i]-sum[q[l]]-L)*(i-q[l]-1+sum[i]-sum[q[l]]-L); 
		while(l+1<=r&&top(i,q[r])*down(q[r],q[r-1])<=top(q[r],q[r-1])*down(i,q[r])) r--;
		q[++r]=i;
	}
	cout<<dp[n];
}

Q2

P3628

A2

\(dp_i=dp_j+(pre_i-pre_j)^2 \times a+(pre_i-pre_j) \times b+c\)

对于决策点 \(j,k\)\(k<j\)\(j\) 优于 \(k\)

\(dp_j+(pre_i-pre_j)^2 \times a+(pre_i-pre_j) \times b+c>dp_k+(pre_i-pre_k)^2 \times a+(pre_i-pre_k) \times b+c\)

\(dp_j+(pre_i-pre_j)^2 \times a+(pre_i-pre_j) \times b>dp_k+(pre_i-pre_k)^2 \times a+(pre_i-pre_k) \times b\)

\(dp_j+(pre_i^2+pre_j^2-2 \times pre_i \times pre_j) \times a+pre_i \times b-pre_j \times b\)

\(dp_j+a \times pre_i^2+a \times pre_j^2-2a \times pre_i \times pre_j+pre_i \times b-pre_j \times b\)

\(dp_j+a \times pre_j^2-2a \times pre_i \times pre_j-pre_j \times b>dp_k+a \times pre_k^2-2a \times pre_i \times pre_k-pre_k \times b\)

\(dp_j+a \times pre_j^2-dp_k-a \times pre_k^2+pre_k \times b-pre_j \times b>2a \times pre_i \times pre_j-2a \times pre_i \times pre_k\)

\(2a \times pre_i \times pre_j-2a \times pre_i \times pre_k<dp_j+a \times pre_j^2-dp_k-a \times pre_k^2+pre_k \times b-pre_j \times b\)

\(2a \times pre_i \times (pre_j-pre_k)<dp_j-dp_k+a \times pre_j^2-a \times pre_k^2+pre_k \times b-pre_j \times b\)

\(2a \times pre_i<(dp_j-dp_k+a \times pre_j^2-a \times pre_k^2+pre_k \times b-pre_j \times b)/(pre_j-pre_k)\)

两边同样具有单调性。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e6+114;
int sum[maxn],q[maxn];
int dp[maxn];
int n,m,a,b,c;
int top(int i,int j){
	return dp[i]-dp[j]+a*sum[i]*sum[i]-a*sum[j]*sum[j]+sum[j]*b-sum[i]*b;
}
int down(int i,int j){
	return sum[i]-sum[j];
}
signed main(){
		cin>>n;
		cin>>a>>b>>c; 
		for(int i=1;i<=n;i++) cin>>sum[i];
		sum[0]=dp[0]=0;
		int l=1,r=0;
		q[++r]=0;
		for(int i=1;i<=n;i++) sum[i]+=sum[i-1];
		for(int i=1;i<=n;i++){
			while(l+1<=r&&2*a*sum[i]*down(q[l+1],q[l])<top(q[l+1],q[l])) l++;
			dp[i]=dp[q[l]]+(sum[i]-sum[q[l]])*(sum[i]-sum[q[l]])*a+(sum[i]-sum[q[l]])*b+c; 
			//val(r,i) < val(r-1,r) r-- 
			while(l+1<=r&&top(i,q[r])*down(q[r],q[r-1])>=top(q[r],q[r-1])*down(i,q[r])) r--;
			q[++r]=i;
		}
		cout<<dp[n];
}

Q3

P2900

A3

先把所有土地按照长度排序,各位读者请自行证明排序后最优方案下总是取连续的土地,因而可以转化为序列分割类问题

\(dp_i=dp_j+ \max(j+1,i)(b_i) \times a_i\)

对于决策点 \(j,k\)\(k<j\)\(j\) 优于 \(k\)

\(dp_j+ \max(j+1,i)(b_i) \times a_i<dp_k+ \max(k+1,i)(b_i) \times a_i\)

$ \max(j+1,i)(b_i) \times a_i- \max(k+1,i)(b_i) \times a_i<dp_k-dp_j$

\(a_i \times ( \max(j+1,i)(b_i)- \max(k+1,i)(b_i))<dp_k-dp_j\)

\(a_i<(dp_k-dp_j)/( \max(j+1,i)(b_i)- \max(k+1,i)(b_i))\)

额外用一个线段树维护 \(\max\) 函数即可。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e6+114;
int q[maxn];
int dp[maxn];
struct Node{
	int a,b;
}chifan[maxn];
int tree[maxn*4];
void pushup(int cur){
	tree[cur]=max(tree[cur*2],tree[cur*2+1]); 
}
void build(int cur,int l,int r){
	if(l==r){
		tree[cur]=chifan[l].b;
		return;
	}
	int mid=(l+r)/2;
	build(cur*2,l,mid);
	build(cur*2+1,mid+1,r);
	pushup(cur);
}
int ask(int cur,int lt,int rt,int l,int r){
	if(rt<l||r<lt){
		return 0;
	}
	if(l<=lt&&rt<=r){
		return tree[cur];
	}
	int mid=(lt+rt)/2;
	int sum=0;
	sum=max(sum,ask(cur*2,lt,mid,l,r));
	sum=max(sum,ask(cur*2+1,mid+1,rt,l,r));
	return sum;
}
bool cmp(Node A,Node B){
	return A.a<B.a; 
}
int n;

int top(int j,int k){
	return dp[k]-dp[j];
}
int down(int i,int j,int k){
	return ask(1,1,n,j+1,i)-ask(1,1,n,k+1,i);
}
signed main(){
		cin>>n;
		for(int i=1;i<=n;i++) cin>>chifan[i].a>>chifan[i].b;
		sort(chifan+1,chifan+n+1,cmp);
		build(1,1,n);
		dp[0]=0;
		int l=1,r=0;
		q[++r]=0;
		for(int i=1;i<=n;i++){
			while(l+1<=r&&chifan[i].a*down(i,q[l+1],q[l])<top(q[l+1],q[l])) l++;
			dp[i]=dp[q[l]]+ask(1,1,n,q[l]+1,n)*chifan[i].a; 
			while(l+1<=r&&top(i,q[r])*down(n,q[r],q[r-1])<=top(q[r],q[r-1])*down(n,i,q[r])) r--;
			q[++r]=i;
		}
		cout<<dp[n];		
}

Q4

P2120

A4

\(dp_i=dp_j+(\sum_{k=j+1}^{i} p_k \times (x_i-x_k))+c_i\)

\(dp_i=dp_j+(\sum_{k=j+1}^{i} p_k \times x_i-p_k \times x_k)+c_i\)

\(dp_i=dp_j+(\sum_{k=j+1}^{i} p_k \times x_i)-(\sum_{k=j+1}^{i} p_k \times x_k)+c_i\)

\(dp_i=dp_j+x_i \times (\sum_{k=j+1}^{i} p_k)-(\sum_{k=j+1}^{i} p_k \times x_k)+c_i\)

令 $chifan_i=\sum_{j=1}^{i} p_j \times x_j $ 以及 \(pre_i=\sum_{j=1}^{i} p_j\)

\(dp_i=dp_j+x_i \times (pre_i-pre_j)-(chifan_i-chifan_j)+c_i\)

对于决策点 \(j,k\)\(k<j\)\(j\) 优于 \(k\)

\(dp_j+x_i \times (pre_i-pre_j)-(chifan_i-chifan_j)+c_i<dp_k+x_i \times (pre_i-pre_k)-(chifan_i-chifan_k)+c_i\)

\(dp_j-pre_j \times x_i+chifan_j<dp_k-pre_k \times x_i+chifan_k\)

\(dp_j+chifan_j-chifan_k-dp_k<pre_j \times x_i-pre_k \times x_i\)

\(x_i \times (pre_j-pre_k)>(dp_j-dp_k+chifan_j-chifan_k)\)

\(x_i>(dp_j-dp_k+chifan_j-chifan_k)/(pre_j-pre_k)\)

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e6+114;
int sum[maxn],q[maxn];
int chifan[maxn],c[maxn],p[maxn],x[maxn];
int dp[maxn];
int n,m;
int top(int j,int k){
	return dp[j]-dp[k]+chifan[j]-chifan[k];
}
int down(int j,int k){
	return sum[j]-sum[k];
}
void init(){
	for(int i=1;i<=n;i++){
		sum[i]=sum[i-1]+p[i]; 
	}
	for(int i=1;i<=n;i++){
		chifan[i]=chifan[i-1]+p[i]*x[i];
	}
} 
signed main(){
		cin>>n;
		for(int i=1;i<=n;i++) cin>>x[i]>>p[i]>>c[i];
		init();
		dp[0]=0;
		int l=1,r=0;
		q[++r]=0;
		for(int i=1;i<=n;i++){
			while(l+1<=r&&x[i]*down(q[l+1],q[l])>top(q[l+1],q[l])) l++;
			dp[i]=dp[q[l]]+x[i]*(sum[i]-sum[q[l]])-(chifan[i]-chifan[q[l]])+c[i];
			while(l+1<=r&&top(i,q[r])*down(q[r],q[r-1])<=top(q[r],q[r-1])*down(i,q[r])) r--;
			q[++r]=i;
		}
		if(p[n]==0) dp[n]-=c[n];
		cout<<dp[n];
		return 0;
}

总结

一般来说,为了兼顾单调性以及不被贪心暴踩,斜率优化 dp 带有一个平方项

不过只要对于决策点 \(j,k\)\(k<j\) 能表述成 \(f(i) > g(j,k)\) (\(g(j,k)\) 常常为斜率的形式,因此叫做斜率优化)且两边单调的形式,都可以斜率优化,不过有时候这个式子更为灵活,需要变通

原文链接:https://www.cnblogs.com/chifan-duck/p/17304555.html

本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:斜率优化入门 - Python技术站

(0)
上一篇 2023年4月17日
下一篇 2023年4月17日

相关文章

  • Python常见数字运算操作实例小结

    下面是详细讲解“Python常见数字运算操作实例小结”的完整攻略。 Python常见数字运算操作 Python是一种强大的编程语言,提供了丰富的数字运算操作。下面介绍Python常见的数字运算操作。 加法、减法、乘法和除法 加法、减法、乘法和除法是Python中最基本的数字运算操作,可以使用加号、减号、乘号和除号来实现。 下面是一个Python实现加法、减法…

    python 2023年5月14日
    00
  • PHP 数据结构队列(SplQueue)和优先队列(SplPriorityQueue)简单使用实例

    下面我来为大家详细讲解一下“PHP 数据结构队列(SplQueue)和优先队列(SplPriorityQueue)简单使用实例”的攻略。 一、SplQueue 首先,我们先来介绍一下SplQueue。SplQueue是一个双向队列,它基于一个双向链表实现,可以在队列的两端插入和删除元素,既可以按照先进先出的顺序来操作队列,也可以反过来按照先进后出的顺序来操作…

    数据结构 2023年5月17日
    00
  • python 人工智能算法之随机森林流程详解

    Python人工智能算法之随机森林流程详解 随机森林是一种常用的机器学习算法,它可以用于分类和回归问题。本文将详细介绍Python中随机森林的流程,包括数据预处理、模型训练和模型评估等步骤。 1. 数据预处理 在使用随机森林算法之前,需要对数据进行预处理。具体来说,需要进行以下步骤: 1.1 数据清洗 数据清洗是指对数据进行去重、缺失值处理、异常值处理等操作…

    python 2023年5月14日
    00
  • 【ACM算法竞赛日常训练】DAY4题解与分析【树】【子序列】| 组合数学 | 动态规划

    DAY4共2题: 树(组合数学) 子序列(dp,数学) ? 作者:Eriktse? 简介:19岁,211计算机在读,现役ACM银牌选手?力争以通俗易懂的方式讲解算法!❤️欢迎关注我,一起交流C++/Python算法。(优质好文持续更新中……)?? 原文链接(阅读原文获得更好阅读体验):https://www.eriktse.com/algorithm/109…

    算法与数据结构 2023年4月18日
    00
  • python实现汉诺塔递归算法经典案例

    Python实现汉诺塔递归算法经典案例 汉诺塔问题是计算机科学中的经典问题,它是一个递归问题,可以用递归算法来解决。本文将详细讲解Python实现汉诺塔递归算法的完整攻略,包括算法原理、Python实现过程和示例说明。 算法原理 汉诺塔问题是一个经典的递归问题,它的基本思想是将一个大问题分解成若干个小问题,然后逐个解决这些小问题,最终得到大问题的解。具体来说…

    python 2023年5月13日
    00
  • C语言二叉树的概念结构详解

    C语言二叉树的概念结构详解 什么是二叉树 二叉树是一种特殊的树形结构,它由一个根节点和若干个子树组成,其中每个节点都最多有两个子节点,分别称为它的左子节点和右子节点。 二叉树的结构 一个二叉树通常由以下几个结构组成: 数据域:存储节点所包含的数据 左节点:节点左侧的子节点,如果为空节点,则表示当前节点没有左子树 右节点:节点右侧的子节点,如果为空节点,则表示…

    数据结构 2023年5月17日
    00
  • Java数据结构之实现哈希表的分离链接法

    Java数据结构之实现哈希表的分离链接法 哈希表是一种非常常用的数据结构,它将数据存储在一个数组中,每个数组元素都存储着链表中的一个节点,这样可以实现高效的数据存储和查找操作。在哈希表中,我们可以通过哈希函数将关键字映射到数组中的特定位置。 但是,当哈希表的负载因子过高时,就会造成哈希冲突,这意味着两个或更多的关键字映射到了同一个数组位置。一种常见的解决方案…

    数据结构 2023年5月17日
    00
  • C++数据结构的队列详解

    C++数据结构的队列详解 队列是什么? 队列是一种先进先出(First In First Out, FIFO)的数据结构,类似于现实生活中的排队等待服务。 队列中的数据按照先进先出的原则被处理。新的元素只能被插入在队列的末尾,而旧的元素只能从队列的开头被删除。因此,队列的末尾称为队尾,队列的开头被称为队头。 队列的实现方式 数组实现方式 队列可以使用数组实现…

    数据结构 2023年5月17日
    00
合作推广
合作推广
分享本页
返回顶部