USACO 5.4 tour的dp解法

题意:有n个点排成序列,两个人甲乙从1出发,到达n,中间的点不允许到达两次,只能从左向右走,问最多两人访问多少点。

(膜大佬)

解:

dp

f(i, j) 表示甲到了i点,乙到了j点,两人最多访问了多少点。

关键性质:f(i, j) = f(j, i)   ***

分析这个问题

(1) f(i, j) = 0  (i == j)

  从而i始终不等于j

深入分析这个问题:

甲与乙的路径必然是相互交叉的!!!

我在dp转移的时候,我保证

f(i, j) = max{ f(k, j) + 1 } (i到k有边),max{k, j} <= i

这样,转移一定是合法的。

而且,必然能**覆盖到**最优解!!,因为最优解必然是一个相互交叉的情况。

不能保证每个 f(i, j) 是最优解,但是可以保证 max{ f(i, n) + 1} (i到n有边)必然是最优解。

原文地址:https://www.cnblogs.com/lawyer/p/6083422.html