- Java锁的逻辑(结合对象头和ObjectMonitor)
- 还在用饼状图?来瞧瞧这些炫酷的百分比可视化新图形(附代码实现)⛵
- 自动注册实体类到EntityFrameworkCore上下文,并适配ABP及ABPVNext
- 基于Sklearn机器学习代码实战
斜率优化是一种经典的单调队列优化类型, 虽然它的名字很高大上 ,但是其思想内核非常简单,这篇博客就是用来帮助各位快速入门的 。
提示:本博客以单调队列的思想理解斜率优化 。
dp 优化可以怎么分类?
数据结构维护决策点集的插入与查找 。
算法维护决策点集大小,取出无用决策点 。
而斜率优化 dp 属于第二者,且常常用于优化序列分割问题 。
P3195 。
先列出一个朴素的 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];
}
P3628 。
\(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];
}
P2900 。
先把所有土地按照长度排序,各位读者请自行证明排序后最优方案下总是取连续的土地,因而可以转化为序列分割类问题 。
\(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];
}
P2120 。
\(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)\) 常常为斜率的形式,因此叫做斜率优化)且两边单调的形式,都可以斜率优化,不过有时候这个式子更为灵活,需要变通 。
最后此篇关于斜率优化入门的文章就讲到这里了,如果你想了解更多关于斜率优化入门的内容请搜索CFSDN的文章或继续浏览相关文章,希望大家以后支持我的博客! 。
Hive —— 入门 Hive介绍 Apache Hive是一款建立在Hadoop之上的开源数据仓库系统,可以将存储在Hadoop文件中的结构化、半结构化数据文件映射为一张数据库表,基于表提供了一
HBase —— 入门 HBase介绍 HBase是一个分布式的、面向列的开源数据库,该技术来源于 Fay Chang 所撰写的Google论文“Bigtable:一个结构化数据的分布式存储系统”
零:前端目前形势 前端的发展史 HTML(5)、CSS(3)、JavaScript(ES5、ES6):编写一个个的页面 -> 给后端(PHP、Python、Go、Java) ->
在本教程中,您将了解在计算机上运行 JavaScript 的不同方法。 JavaScript 是一种流行的编程语言,具有广泛的应用程序。 JavaScript 以前主要用于使网页具有交
我曾经是一个对编程一窍不通的小白,但因为对互联网世界的好奇心和求知欲的驱使,我踏入了编程的殿堂。在学习的过程中,我发现了一门神奇的编程语言——Python。Python有着简洁、易读的语法,让初学者能
嗨,亲爱的读者们! 今天我要给大家分享一些关于Python爬虫的小案例。你是否曾为了获取特定网页上的数据而烦恼过?或者是否好奇如何从网页中提取信息以供自己使用?那么,这篇文章将会给你一些启示和灵感。
关闭。这个问题是opinion-based 。目前不接受答案。 想要改进这个问题吗?更新问题,以便 editing this post 可以用事实和引文来回答它。 . 已关闭 8 年前。 Improv
我想创建一个像https://apprtc.appspot.com/?r=04188292这样的应用程序。我对 webrtc 了解一点,但无法掌握 google app-engine。如何为 java
我刚刚开始使用 Python 并编写了一个简单的周边程序。但是,每当我在终端中键入 python perimeter.py 时,都会收到以下错误,我不知道如何解决。 >>> python perime
Redis有5个基本数据结构,string、list、hash、set和zset。它们是日常开发中使用频率非常高应用最为广泛的数据结构,把这5个数据结构都吃透了,你就掌握了Redis应用知识的一半了
创建发布web项目 具体步骤: 1.在开发工具中创建一个dynamic web project helloword 2.在webContent中创建index.html文件 3.发布web应用到
如果你在 Ubuntu 上使用终端的时间很长,你可能会希望调整终端的字体和大小以获取一种良好的体验。 更改字体是一种最简单但最直观的 Linux 的终端自定义 的方法。让我
1. 前言 ADODB 是 Active Data Objects Data Base 的简称,它是一种 PHP 存取数据库的函式组件。现在 SFS3 系统 (校园自由软件交流网学务系统) 计划的
我对 neo4j 完全陌生,我很抱歉提出这样一个基本问题。我已经安装了neo4j,我正在使用shell“localhost:7474/webadmin/#/console/” 我正在寻找一个很好的例子
我正在阅读 ios 4 的核心音频,目的是构建一个小测试应用程序。 在这一点上,我对所有 api 的研究感到非常困惑。理想情况下,我想知道如何从两个 mp3 中提取一些样本到数组中。 然后在回调循环中
关闭。这个问题不符合Stack Overflow guidelines .它目前不接受答案。 要求我们推荐或查找工具、库或最喜欢的场外资源的问题对于 Stack Overflow 来说是无关紧要的,因
我下载了 GNUStep并安装了它,但是我不确定在哪里可以找到 IDE。有谁知道什么程序可以用作 GNUStep IDE/从哪里获取它们?否则,有没有人知道有关如何创建和编译基本 GNUStep 程序
我正在尝试开始使用 Apache Solr,但有些事情我不清楚。通读tutorial ,我已经设置了一个正在运行的 Solr 实例。我感到困惑的是 Solr 的所有配置(架构等)都是 XML 格式的。
请问有没有关于如何开始使用 BruTile 的文档? 我目前正在使用 SharpMap,我需要预缓存切片以加快进程 最佳答案 我今天正在研究这个:)Mapsui项目site严重依赖 SharpMap
尽我所能,我无法让 CEDET 做任何事情。 Emacs 24.3。我下载了最新的 CEDET 快照。我从他的底部(不是这样)Gentle Introduction 中获取了 Alex Ott 的设置
我是一名优秀的程序员,十分优秀!