noip2008 提高组 第三题

来源：百度知道 编辑：UC知道 时间：2024/06/15 08:46:01
第三题传纸条，我知道用动规，但是每个同学只能传一次，我该怎么处理？
本人PASCAL语言

传不传一次并不影响最优结果 因为最优的结果一定不会经过一个同学两次 那样将其中一条路在交叉的那点从另一边走就有了更优解 所以那样一定不是最优解。。。 然后就按原始的动规就行了