AcWing
  • 首页
  • 题库
  • 题解
  • 分享
  • 问答
  • 活动
  • 应用
  • 吐槽
  • 登录/注册

【提高版】DP知识笔记8

作者: 作者的头像   有猷 ,  2020-05-17 21:34:09 ,  阅读 479


7


2

本期笔记的内容为 单调队列优化DP 与 斜率优化DP

相关链接:

1.往期笔记: 查看
2.来源:yxc老师的算法提高课


【提高版】DP知识笔记8 $\quad$ 有猷 编


$\color{#00ab00}{思考方式}$:

wjx.png


$\color{#FF0000}{第一部分:单调队列优化}$

例题:

1. 最大子序和

思路:
wjx.png
代码:https://www.acwing.com/activity/content/code/content/268538/

2. 旅行问题

思路:wjx.png
代码:https://www.acwing.com/activity/content/code/content/277068/

3. 烽火传递

思路:wjx.png
代码:https://www.acwing.com/activity/content/code/content/277126/

4.修剪草坪

思路:wjx.png
代码:https://www.acwing.com/activity/content/code/content/305539/

5. 理想的正方形

思路:wjx.png
代码:https://www.acwing.com/activity/content/code/content/305835/


$\color{#FF0000}{第二部分:斜率优化}$

例题:

1. 任务安排1

思路

  • 普通的DP,并未使用斜率优化

wjx.png

时间复杂度:$O(n^2)$

代码:https://www.acwing.com/activity/content/code/content/311193/

2. 任务安排2

思路:

  • 前一题的优化(斜率优化从这里开始)

思路:wjx.png
代码:https://www.acwing.com/activity/content/code/content/317907/

0 评论

你确定删除吗?

© 2018-2021 AcWing 版权所有  |  京ICP备17053197号-1
联系我们  |  常见问题
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标
请输入绑定的邮箱地址
请输入注册信息