四边形不等式与凸完全单调性在动态规划中的应用

"这篇资料主要讨论了凸完全单调性在ACM/ICPC竞赛中的应用，作者为杨哲，涉及四边形不等式、决策单调性和动态规划问题的解决方案。" 文章深入探讨了数学和算法领域中的一个重要概念——凸完全单调性。首先，它定义了一个权函数w(i,j)，如果满足w(x,i+1) - w(x,i) 随x单调不增的条件，那么该函数就被认为具有凸完全单调性。这一特性能够确保w(x,i+1) + w(x+1,i) ≥ w(x,i) + w(x+1,i+1)，这是四边形不等式的核心。四边形不等式不仅能够推出凸完全单调性，而且在证明某些不等式和优化问题中起到关键作用。 接着，文章阐述了在动态规划问题中，凸完全单调性与决策单调性的关系。在需要找到最小总成本划分序列的问题中，状态转移方程展示了决策单调性的概念。如果某个决策i在某个时刻x比决策j更优（即t(i,x) - t(j,x)较小），那么在所有后续时刻y>x，决策i也会保持优于决策j。这表示最佳决策随着x的增加而单调不减，从而可以使用B[i]来记录决策i优于所有之前决策j的最小x值。 利用决策单调性，可以确定哪些决策是无用的。如果B[i] - B[j]，意味着决策i无法在任何时刻优于决策j，因此可以剔除决策i。通过找到一系列有用的决策i1, i2, ..., ik，并按照它们对应的B[i]值排序，可以高效地求解动态规划问题。 最后，文章提到在求解f[x]时，选择j=max{j:B[ij] - x, j-k}，对应的决策ij将是当前x处的最佳决策，从而确定f[x]的值。这种方法极大地简化了问题的解决过程，尤其在处理复杂优化问题时，凸完全单调性和决策单调性的应用显得尤为重要。 总结起来，这篇资料详尽地介绍了凸完全单调性及其在ACM/ICPC竞赛中解决问题的应用，特别是如何利用这些性质优化动态规划的解法，对于参赛者和对算法感兴趣的读者来说具有很高的学习价值。