我的csdn：https://blog.csdn.net/m0_51780913/article/details/119111678

单调队列优化DP

划定区间取值问题
对于长度为l的区间，每s长度至少有一个数被取，使用动态规划
f(i)表示选第i个数的最小方案
集合划分：可以取i-s+1到i-1的各种方式
因此f[i]=w[i]+min(f[i-m+1],....,f[i-1])
对于后面这一段min(f[i-m+1~i-1])可以使用单调队列优化。

 

​

---

​

凸包优化DP（斜率优化）

 

由状态转移方程：

$$
f[i]=min\{ f[j]+T_{i}(C_i-C_j)+S(C_n-C_j) \}
$$

其中

$$
j=0,1...i-1
$$

我们可以将其整理为以为自变量，为因变量的一次函数形式：

$$
f(j)=(S+T_i)C_j+f(i)-T_iC_i-SC_n
$$

 

因为要最小化f(i),对于本题来说，就是找截距最小值，在图中我们可以发现只需要维护图中的凸包的下边界：

凸包下边界的定义：任意两点连线，在连线上方的点都在凸包的下边界以上

但是只维护凸包的下边界最坏会出现O(n)的情况，因此仍然需要挖掘其他信息：

某点被取当为斜率大于的第一个点的起点

 

 

 

总结：如何在维护凸包中找到截距最小的点：

相当于在于一个单调的队列中，找到第一个大于某一个数的点。因此普遍做法是采用二分法。

其他特殊性质：

1.斜率单调递增，新加的点的横坐标也单调递增(k1<k2<k3)

​ 在查询的时候可以将队头小于当前斜率的点全部删除(删除所有小于k的点)

​ 在插入的时候，把队尾**所有**不满足要求的点全部删除（即不在凸包上）
1. 若
$$
frac{f_2-f_1}{C_2-C_1} \le sumT_i+S
$$
则删除队头

2.若
$$
frac{f_{tt}-f_{tt-1}}{C_{tt}-C_{tt-1}} \ge \frac{f_i-f_{tt}}{C_i-C_{tt}}
$$
则将队尾元素删去

例题：Acwing 301

#include<bits/stdc++.h>
using namespace std;
#define MAXN 300010
typedef long long LL;
​
LL c[MAXN],t[MAXN];
int s,n,m;
int q[MAXN];
LL f[MAXN];
​
int main(){
   scanf("%d%d",&n,&s);
   for(int i=1;i<=n;i++){
       scanf("%lld%lld",&t[i],&c[i]);
       t[i]+=t[i-1],c[i]+=c[i-1];
  }
   
   //初始化
   int hh=0,tt=0;
   q[0]=0;
   for(int i=1;i<=n;i++){
       while(hh<tt&&(f[q[hh+1]]-f[q[hh]])<=(t[i]+s)*(c[q[hh+1]]-c[q[hh]])) hh++;
       int j=q[hh];
       f[i]=f[j]+t[i]*(c[i]-c[j])+s*(c[n]-c[j]);
       while(hh<tt&&(f[q[tt]]-f[q[tt-1]])*(c[i]-c[q[tt]])>=(c[q[tt]]-c[q[tt-1]])*(f[i]-f[q[tt]]))
           tt--;
       q[++tt]=i;
  }
   printf("%lld",f[n]);
   return 0;
}

更一般的情况，T<0时：

此时k无法保证单调性，但新加的点横坐标一定单调递增。因此只能查询，不能删去斜率小于当前点的点。查询的时候只能二分；

队尾仍然删除所有队尾不在凸包上的点

如果T>0,C<0 可以使用反函数，交换x,y

最一般的情况：

考虑C可能小于0且T也可能小于0

队头处理还是二分。队尾的动态维护有序序列则需要平衡树来做了