首页 > 其他分享 >【学习笔记】初次学习斜率优化的代码及笔记

【学习笔记】初次学习斜率优化的代码及笔记

时间:2024-05-05 17:44:25浏览次数:26  
标签:return 2s int 笔记 学习 斜率 while dp

include<bits/stdc++.h>

using namespace std;
int n,m;
int dp[10000],s[6100],q[10000];
int slope(int j,int k)
{
int x=(dp[j]-dp[k]+s[j]s[j]-s[k]s[k])/(s[j]+s[k]);
return x;
}//求斜率
int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
for(int i=1;i<=n;i++)
{
cin>>s[i];
s[i]+=s[i-1];
}
int L=1,R=1;
dp[0]=0;
for(int i=1;i<=n;i++)
{
while(L<R && slope(q[L],q[L+1])<=s[i])L++;
dp[i]=dp[q[L]]+(s[i]-s[q[L]])(s[i]-s[q[L]])+m;
while(L<R && slope(q[R-1],q[R])>slope(q[R],i))R--;
q[++R]=i;
}
cout<<dp[n]<<endl;
}
return 0;
}
/
斜率优化:
1.将转移方程抽象成一个不等式关系,
如本题中由于要求出最小价值,易知转移方程为:dp[i]=min(dp[j-1]+(s[i]-s[j])^2+m) (1<=j<=i)
设此时有两个点,j和k
则如果有dp[j]+(s[i]-s[j])2+m<dp[k]+(s[i]-s[k])2+m
即可知道j优于k
将上不等式展开可得:
dp[j]+s[i]2+s[j]2-2s[i]s[j]<dp[k]+s[i]2+s[k]2-2s[i]s[k];
移项:dp[j]-dp[k]+s[j]2-s[k]2<2s[i]s[j]-2s[i]s[k]
整理:(dp[j]-dp[k]+s[j]2-s[k]2)/(s[j]-s[k])<2s[i];
因为s[i]可看作常数,而左边可抽象成(y1-y2)/(x1-x2)
即斜率,那么只要满足k与j之间斜率满足此不等式,则就有j优于k
若不等号方向改变,则为k优于j
那么求斜率的函数则为
int slope(int j,int k)
{
int x=(dp[j]-dp[k]+s[j]s[j]-s[k]s[k])/(s[j]+s[k]);
return x;
}
2.求得斜率后,便有三种情况(j,k,i)
一,三个点的两条连线斜率均小于2s[i],则分别比较两个斜率,斜率更大的右端点为最优点
二,三个点的两条连线斜率均大于2s[i],则分别比较两个斜率,斜率更大的左端点为最优点
三,三个点的两条连线斜率一大一小,则可以判断的是中间一个点一定不是最优点,可排除
3.排除完后,可发现这些点是成单调递增趋势的,将这些点放入队列中
依次查找符合要求的点
本题中最优点应为满足斜率<2s[i]且位于最右边的点
*/

标签:return,2s,int,笔记,学习,斜率,while,dp
From: https://www.cnblogs.com/Ashkadira/p/18173681

相关文章

  • 集合幂级数学习笔记
    基本操作集合并卷积集合幂卷积定义为:给定两个集合幂级数\(F,G\),计算集合幂级数\(H\)满足:\[\begin{aligned}h_S=\sum_{L\subset2^U}\sum_{R\subset2^U}[L\cupR=S]f_Lg_R\end{aligned}\]我们考虑用类似于FFT的方式,把\(f,g\)按某种线性变换后,然后把问题变成点乘。......
  • 深度学习相关理论
    一、深度学习相关理论1.神经网络概述     2.卷积神经网络CNN ①卷积层——计算方法是大矩阵内部×小矩阵=较小矩阵,作用是特征提取  ②池化层——计算方法是大矩阵通过选取最大值或是平均值变成小矩阵,作用是降维、提高计算效率    3.激活函......
  • 网课-博弈论学习笔记
    Nim游戏\(n=2\)的时候可以用一个巧妙的方法证明:如果两堆石子一样多,则后手可以通过在另一堆上一直模仿先手的行为获胜;如果两堆石子不一样多,则先手可以在第一次取时把两堆变成一样多。结论中出现异或的原因(异或的定义为):\[a\oplus0=a\]\[a\oplusa=0\]\[a\oplusb=......
  • PHP-数据对象学习手册(全)
    PHP数据对象学习手册(全)原文:zh.annas-archive.org/md5/33ff31751d56930c46ef1daf9ca0ebcb译者:飞龙协议:CCBY-NC-SA4.0前言本书将向您介绍PHP5.0版本开始提供的最重要的扩展之一——PHP数据对象,通常称为PDO。PHP由于其简单性和易用性而成为非常流行的Web编程语言......
  • FFmpeg开发笔记(十九)FFmpeg开启两个线程分别解码音视频
    ​同步播放音视频的时候,《FFmpeg开发实战:从零基础到短视频上线》一书第10章的示例程序playsync.c采取一边遍历一边播放的方式,在源文件的音频流和视频流交错读取的情况下,该方式可以很好地实现同步播放功能。但个别格式的音频流和视频流是分开存储的,前面一大段放了所有的音频帧,后......
  • pde复习笔记 第一章 波动方程 第六节 能量不等式、波动方程解的唯一性和稳定性
    能量不等式这一部分需要知道的是能量的表达式\[E(t)=\int_{0}^{l}u_{t}^{2}+a^{2}u_{x}^{2}dx\]一般而言题目常见的问法是证明能量是减少的,也就是我们需要证明\[\dfrac{d}{dt}E(t)\le0\]在计算\(\dfrac{d}{dt}E(t)\le0\)的时候一定会用的题目给的方程条件去凑微分,还会......
  • 8086 汇编学习 Part 9
    端口的读写CPU的邻居CPU内部的寄存器内存单元端口(各种接口卡、网卡,显卡,主板上的接口芯片等)各种芯片工作时,都有一些寄存器由CPU读写从CPU角度,将各寄存器当端口,并统一编制CPU用统一的方法与各种设备通信读写端口的指令在对\([0,255]\)的端口进行读写时,端口......
  • 计算理论导论笔记
    计算理论导论笔记正则语言和自动机(RegularLanguagesandAutomata)DFA确定性有限状态自动机(DeterministicFinitestateAutomata/DFA)由一个五元组\((Q,\Sigma,\delta,q_0,F)\)唯一确定。\(Q\)为状态集合。\(\Sigma\)为字符集。\(\delta:Q\times\Sigma\toQ\)为状态转......
  • 【笔记】C# CancellationToken
    .NET提供了一个类方便用来发出操作取消的信号,这个类就是CancellationToken,它的好处在于它可以在任意数量的线程之间、线程池任务之间、Task之间传递信号,并且所需的代码很简单。通常用于下载超时中断、用户取消任务等情况。CancellationToken通常搭配CancellationTokenSource......
  • Go-编程学习手册(全)
    Go编程学习手册(全)原文:zh.annas-archive.org/md5/5FC2C8948F5CEA11C4D0D293DBBCA039译者:飞龙协议:CCBY-NC-SA4.0前言Go是一种开源编程语言,让程序员可以轻松构建可靠且可扩展的程序。它通过提供简单的语法来实现这一点,使得使用并发习语和强大的标准库编写正确且可预测的代......