为什么贪心总能保持最优解?

P1181 数列分段 Section I

@[木守球](/space/show?uid=121122) 这……显而易见啊,从第一个开始每一段显然越接近m越好,那么就直接挨个加直到撑爆再-1就可以了啊
by 斗神·君莫笑 @ 2018-09-03 23:02:11


@[斗神·君莫笑](/space/show?uid=49644) 你怎么保证不第一个独立出来的话,后面可能包含的数更多的情况?
by 木守球 @ 2018-09-04 21:59:57


@[木守球](/space/show?uid=121122) 当你有一支牙膏,快用完了,但是挤挤还能用的时候,是直接丢弃这支新开一支牙膏好一些呢还是接着用这支牙膏好一些? 同理,当你有一个组合数还能塞数进去的时候,是接着塞更优呢还是给他直接丢弃这个组合数再新开个数塞进去更优?
by 隐心 @ 2018-09-07 20:12:57


@[木守球](/space/show?uid=121122) 这就是最简单得贪心问题了,你是想把划分得数尽量接近m呢?还是把它划分在后面的数呢?显然,划分到后面是多余且不是最优得操作
by 蒟蒻小菜鸡 @ 2018-11-05 13:19:00


@[木守球](/user/121122) 因为这玩意儿是数列,人家是有顺序的,你和我刚开始想的一样蛤蛤蛤;
by 计科1802晁琪洛 @ 2020-01-18 20:56:24


|