有人会这个贪心的证明吗?

P1315 [NOIP2011 提高组] 观光公交

选k次的就是每次的全局最优,并非局部最优。
by ppip @ 2023-01-26 19:28:22


@[ppip](/user/374433) 但是每次选取并不独立啊,选一个带来的增益都与之前选位置的有关。您说的全局最优依然是对于每次而言。换言之就是为什么不可以先选一些虽然不让当前最优的位置,但是可能让后面的某次选择相对增益更大呢。
by huazai676 @ 2023-01-26 19:36:04


不是很会了,感觉一个车站之前的加速次数是固定的
by ppip @ 2023-01-26 19:44:18


同问,题解看不懂,贪心不证明根本无法理解(我甚至想问,这些贪心怎么推出来的,感觉有问题啊)
by kelanjie @ 2023-02-22 22:01:17


@[kelanjie](/user/699110) 同看不懂,一年前做的时候不会,现在还是看不懂题解(
by bbjr @ 2023-02-27 21:15:22


|