洛谷:P2392:kkksc03考前临时抱佛脚


洛谷:P2392:kkksc03考前临时抱佛脚

Table of Contents

题目

P2392:kkksc03考前临时抱佛脚

分析

因为本题出现在DFS的章节,所以不用多想,用DFS去解决。

核心点在于:对于每个要处理的科目中的每个习题集,都有两种可能:左脑去学习;或者右脑去学习。这是这道题目唯一的“坑”吧。

答案

Solution

思考

这道题目的思考点有两个。

首先,代码中没有出现DFS中常见的回溯。这是因为左右两脑的路径是完全独立的,也不存在某个题目会被复用的情况,我们只是顺序地一道题一道题安排罢了。所以,每个分支都有全面的科目安排,不依赖任何前置科目的安排。

其次,这道题看起来很像贪心,而且贪心的策略也很简单:左边、右边来回放,哪边“轻”(负担小)就放哪边。但很不幸,按照这个逻辑写好的代码没法通过任何测试——只能通过题目中的样本数据!

洛谷也真的是够坏的了。

贪心不成立的一个反例,同样来自洛谷

4 3 3 2 2

如果按照贪心,最后的结果是:[4 2] [3 3 2],最长时间是8。但是[4 3] [3 2 2]更平衡,可以得到7

类似题目:

上一篇 下一篇