动态规划与凸完全单调性：理论与应用

"这篇文档探讨了在解决动态规划问题中的一种强化策略——凸完全单调性的概念及其应用。文章作者是西安市第一中学的杨哲，主要涉及ACM和NOIP（全国青少年信息学奥林匹克竞赛）相关的知识领域。内容包括四边形不等式、凸完全单调性、决策单调性，并对这些概念进行了深入的解释和举例说明。" 在动态规划问题中，凸完全单调性是一种非常重要的性质，它涉及到权函数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)，那么该权函数被认为是满足凸完全单调性的。这个性质可以推广，当k>0时，w(x,i+k)-w(x,i)和w(i+k,x)-w(i,x)都是随x单调非减的。由此引出了四边形不等式：对于任意的a-b-c-d，都有w(a,d)+w(b,c)≥w(a,c)+w(b,d)。四边形不等式是凸完全单调性的另一种表述形式。 在一类特定问题中，我们需要将序列划分为若干子段，每段的费用由w(i,j)给出，目标是最小化所有子段费用之和。在这种情况下，我们可以构建动态规划的状态转移方程，定义t(i,x)=f[i]+w(i,x)。如果在某个时刻，t(i,x)-t(j,x)（i<j）表明决策i始终不如决策j，即f[x]的决策随着x单调不减，这就是决策的单调性。 在解决这类问题时，B[i]被用来记录使得决策i优于所有之前决策j (j<i)的最小的x值，即B[i]=min{x:t(i,x)<t(j,x)对所有j<i成立}。如果B[i]-B[j]，则决策i是无用的。因此，所有有用决策i1,i2,...,ik（满足i1<i2<...<ik）会使得B[i1]<B[i2]<...<B[ik]。求解f[x]时，选取j=max{j:B[ij]-x,j-k}，此时决策ij是最佳的，即f[x]=t(ij,x)。 总结来说，这篇文档详细介绍了动态规划中的凸完全单调性，它不仅有助于理解和解决动态规划问题，而且在优化决策序列和减少无效决策方面提供了有力工具。通过四边形不等式和决策单调性的理解，读者能够更有效地处理涉及这些特性的算法问题。