关于新版书中应用四边形不等式证明决策单调性的不严谨

[CreMicro]

建议：特别说明一点，当同时存在多个转移值相等的 p[i] 时，只取下标最大的 p[i] , 不会影响答案

因为事实上，对于一个 i 可能有一段的结果相同的 p[i] (设为 [l[i], r[i]] ),对于一个 i' > i , 可能有一段结果相同的 p[i'] (设为 l[i'] , r[i']), 同时完全有可能这两段有长度大于1的重叠部分(r[i] ,l[i' ],且 r[i] < l[i'] )，则 p[i] 可以取 l[i'], p[i'] 可以取 r[i] , 此时就“不满足” 决策单调性了

但其实这并不会影响答案正确性，因为最小值结果相同的决策可任意取

因此建议说明这里的 p[i] 取得实际上是满足使得 dp [i] 最小后下标最大的

[tabbbbbb]

    您好，您的邮件已收到，谢谢！