求助断环成链正确性

P2512 [HAOI2008] 糖果传递

你想啊,如果相邻的两个人都传递了一次糖果,那就相当于啥也没干。
by Suuon_Kanderu @ 2021-01-17 17:27:49


~~这种东西为什么要知道为什么呢~~
by Stinger @ 2021-01-17 17:29:57


@[zhangqs](/user/361308) /?
by MatrixCascade @ 2021-01-17 17:35:42


@[史旺·坎德尔](/user/226148) 不是,意思是既不会 $a->b$,也不会 $b->a$
by Cry_For_theMoon @ 2021-01-17 17:35:47


我感觉一定可以构造一个答案相等的方案,使得其中两个相邻之间的传递被消掉
by __gcd @ 2021-01-17 17:58:27


比如说 $i\rightarrow i+1$,我可以让 $i$ 传给 $i-1$,然后绕一圈传到 $i+1$,这样 $i$ 和 $i+1$ 之间就没有传递了
by __gcd @ 2021-01-17 17:59:44


@[Cry_For_theMoon](/user/340632)
by __gcd @ 2021-01-17 17:59:57


@[__gcd](/user/149192) 这点我想到了qwq,但这样如何保证答案最优性qwq
by Cry_For_theMoon @ 2021-01-17 19:08:32


@[Cry_For_theMoon](/user/340632) 不是,假设所有人都向右边传$a_i$ 珂糖果,就相当于向右传了 $a_i - \min^{n}_{i=1}a_i$ 珂糖果,肯定不是最优的。
by Suuon_Kanderu @ 2021-01-17 19:21:36


@[史旺·坎德尔](/user/226148) 但是还可以向左传啊,或者说您这里的传递带负数以实现向左传的目的?
by Cry_For_theMoon @ 2021-01-17 19:55:46


| 下一页