闵可夫斯基和 优化 dp
\(\left( \min/\max,+\right)\) 卷积
形如：
\[f_i=\max ^i_{j=0}/\min ^i_{j=0} {g_j+h_{i-j}}
\]
的式子被称为 \(\left( \min/\max,+\right)\) 卷积。
闵可夫斯基和
以 \(\min\) 为例，要求 \(g,h\) 形成下凸包，对 \(g,h\) 进行差分（由于下凸包，\(\Delta g\) 与 \(\Delta h\) 显然是不增的），那么 \(f_i\) 相当于在 \(\Delta g\) 和 \(\Delta h\) 中选两个前缀（差分数组的前缀和是原数组，是不是很神奇（？）），要求长度和为 \(i\) 且使得和最小，归并排序后取前 \(i\) 个即可。
\(\max\) 同理。
优化 dp 时常见的应用是使 \(g\) 为 \(f_{i-1}\)，\(h\) 为权值函数。
slope trick 优化 dp
slope trick 可以用于快速维护分段一次、连续的凸性函数。
它的思想是维护斜率而非函数本身，当斜率的取值范围小时维护拐点，当定义域较窄时可以维护斜率序列（用 set 全存起来就好了）
可以维护的操作：
-
相加：将最优决策点、定义域左右端点直接加上权值。
-
取前/后缀 min：去掉一部分。
-
求 min：维护 \(k=0\) 的决策点（区间）即可。
-
全局平移/翻转：单独处理最优决策点后全局打标记。
以下为一个例子：
st.insert({0,k});
int L=0,siz=k,ans=0;
//ans 为最优决策点，L 为定义域左端点，siz 为定义域大小
for(int i=1;i<=n;i++){L+=a[i]-b[i];siz+=b[i]*2;ans+=b[i]*c[i];st.insert({c[i],b[i]});st.insert({-c[i],b[i]});while(R>k){//求minauto t=st.end();t--;zxc now=*t;st.erase(t);int shan=min(R-k,now.x);siz-=shan;now.x-=shan;if(now.x){st.insert(now);}}while(L<0){//求minauto t=st.begin();zxc now=*t;st.erase(t);int shan=min(0-L,now.x);L+=shan;siz-=shan;ans+=now.k*shan;now.x-=shan;if(now.x){st.insert(now);}}
}