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

相关链接：

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

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

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

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

例题：

1. 最大子序和

思路：

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

2. 旅行问题

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

3. 烽火传递

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

4.修剪草坪

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

5. 理想的正方形

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

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

例题：

1. 任务安排1

思路

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

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

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

2. 任务安排2

思路：

• 前一题的优化（斜率优化从这里开始）

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