一个凸性有关的 dp

学术版

complexor @ 2025-06-12 14:52:33

设 f_{0\sim n},g_{0\sim m} 是两个下凸序列（差分序列单调不降），那么通过如下方式构造 h：

h_i=\min_{j=0}^n\{f_j+g_{i-j}+j(i-j)\}

得到的 h 是下凸的吗？ 如果是能快速计算吗？

|