前几天想练练思维，所以从cf上随便找了一道dp题，看完题意后第一感觉很简单，就是简单的区间dp题，但是看到数据范围的我顿时就懵了，（1≤n≤105）

emmmmmmmm，按照普通的思路肯定会超时的。。。。

想了很久，总感觉可以利用前面已经经历过的点进行优化，但是不知道该怎么动手

问了度娘后发现这题需要用到单调栈还是斜率优化之类的。。。。。

额。。。之前听说过斜率优化，但是没有真正的学习过，然后找了网上大佬的博客学习了一番，终于学会了一点皮毛

https://www.cnblogs.com/ka200812/archive/2012/08/03/2621345.html

这位大佬给的图好像反了。。。但是讲解非常的通俗易懂

https://blog.csdn.net/lxc779760807/article/details/51366552

https://www.cnblogs.com/orzzz/p/7885971.html

大米饼：https://www.cnblogs.com/Paul-Guderian/p/7259491.html

做完大米饼大佬博客推荐的题目后，我总结了一点经验

我们遇到斜率优化dp时，和其他dp一样，首先我们要推出它的状态转移方程,例如

f[i]=min(f[j]+add(i,j))(j<i)

然后将状态转移方程转化为

y   =   kx   +   b     的形式

只与j有关  k只与i有关  我们要求的f[i]

x只与j有关

然后根据x的单调性和k的正负判断该建立一个怎样的凸包（用排列组合算有八种（23），但是我只确定了四种的，以后再补充吧）

最新文章

  1. XMLHTTP中setRequestHeader方法和参数
  2. php 使用GD库上传图片以及创建缩略图
  3. DrawTool多重笔之前奏 =&gt; 通过InkAnalyzer实现图形识别
  4. 基于opencv的小波变换
  5. [C++基础]在构造函数内部调用构造函数
  6. robotframework代码定位感悟
  7. 在 Windows 上测试 Redis Cluster的集群填坑笔记
  8. iOS 证书详情介绍
  9. 为什么String类是不可变的？
  10. 保存单文件为mhtml
  11. openssl 生成证书基本原理
  12. 学web前端开发有前途吗
  13. springMvc(一)
  14. 关于bootstrap两个模态框的问题
  15. Java Web 项目发布到Tomcat中三种部署方法
  16. 高性能缓存Caffeine
  17. ubuntu下安装mysql和配置远程访问
  18. Jquery 组 表单select交互选项
  19. 12.double的int方
  20. 动态显示checkbox选中条数

热门文章

  1. vue进入页面时不在顶部，检测滚动返回顶部按钮
  2. python3之面向对象编程理解
  3. springboot学习入门简易版一---springboot2.0介绍
  4. java 原子操作(1) CAS
  5. 网络基础 InetAddress
  6. 七年总结常用 Git 命令清单
  7. Excel导入+写入数据库
  8. Android笔记（十九） Android中的Fragment
  9. unittest 运行slenium（二）---打开浏览器及元素操作
  10. FDD-LTE上下行带宽一样的,为什么上下行流量差别这么大