有同学能证明贪心是对的吗?

P1167 刷题

WaltVBAlston @ 2021-10-23 08:58:36

RT,我感觉这道题dp才是正解,但是造不出一组数据卡贪心。题解区清一色的贪心但是没有dp,有同学能证明贪心是对的吗


by rui_er @ 2021-10-23 09:01:12

你做一道更难的题显然不如更简单的题更优


by JRzyh @ 2021-10-23 09:01:55

@Andy_2006 当然是做时间越短的越好了


by SfumatoCannon_ @ 2021-10-23 09:03:15

做简单的题和做难的题对答案的贡献都是一样的,那为什么不做简单的题(


by 断清秋 @ 2021-10-23 09:03:52

LZ读错题了吧……这难道不是显然贪心做时间最少的吗


by WaltVBAlston @ 2021-10-23 09:05:31

@rui_er @Z_LOVE_OI @SfumatoCannon_ @断清秋

我好想有点懂了,决定把贪心和dp都打一遍


by RGYZ @ 2021-10-23 09:06:45

@rui_er 大神,能请教您个问题吗?您做这么多题,是固定每天刷多少题,还是周六日集中刷呢,想估计一下自己一年能刷多少题


by abcdeffa @ 2021-10-23 09:06:59

@Andy_2006 这题贪心正确性不是显然么。

你考虑如果选的个数 k 的总时间不是最小的话,即它们在排好序的序列中的位置是断开的,那么我们一定能够选前 k 个以获得最小的总时间,而显然这种方案是不会更劣的。


|