【学习笔记】闵可夫斯基和
概述
用于优化 \((\max/\min,+)\) 卷积，形如：
\[f_i=\max_{j=0}^i/\min_{j=0}^i \{g_j+h_{i-j}\}
\]
要求 \(g,h\) 具有凸性。
算法流程
以 \(\max\) 为例，要求 \(g,h\) 形成上凸包，对 \(g,h\) 差分，那么 \(f_i\) 相当于在 \(\Delta g\) 和 \(\Delta h\) 中选两个前缀，要求长度和为 \(i\)，权值和最大。由于 \(\Delta g\) 和 \(\Delta h\) 都单调不升，那么归并排序之后选前 \(i\) 个数就是最优。
同理 \(\min\) 要求 \(g,h\) 形成下凸包。
vector<int> Minkowski(vector<int> g,vector<int> h){
vector<int> f;
for(int i=(int)g.size()-1;i>=1;--i) g[i]-=g[i-1];
for(int i=(int)h.size()-1;i>=1;--i) h[i]-=h[i-1];
f.resize(g.size()+h.size());
merge(g.begin(),g.end(),h.begin(),h.end(),f.begin(),greater<int>());
for(int i=1;i<f.size();++i) f[i]+=f[i-1];
return f;
}
优化 DP
通常与分治同时使用。
转移方程 \(f_{i,j}=\max_{j=0}^i/\min_{j=0}^i \{f_{i-1,j}+w_{i,i-j}\}\)
若 \(f,w\) 均具有凸性，可以使用闵可夫斯基和优化至 \(O(n)\) 转移，分治可以做到 \(O(n\log n)\)。
例题
待更新。
参考资料
【学习笔记】闵可夫斯基和 - APJifengc