题目
分析
因为本题出现在DFS的章节,所以不用多想,用DFS去解决。
核心点在于:对于每个要处理的科目中的每个习题集,都有两种可能:左脑去学习;或者右脑去学习。这是这道题目唯一的“坑”吧。
答案
思考
这道题目的思考点有两个。
首先,代码中没有出现DFS中常见的回溯。这是因为左右两脑的路径是完全独立的,也不存在某个题目会被复用的情况,我们只是顺序地一道题一道题安排罢了。所以,每个分支都有全面的科目安排,不依赖任何前置科目的安排。
其次,这道题看起来很像贪心,而且贪心的策略也很简单:左边、右边来回放,哪边“轻”(负担小)就放哪边。但很不幸,按照这个逻辑写好的代码没法通过任何测试——只能通过题目中的样本数据!
洛谷也真的是够坏的了。
贪心不成立的一个反例,同样来自洛谷:
4 3 3 2 2
如果按照贪心,最后的结果是:[4 2] [3 3 2]
,最长时间是8
。但是[4 3] [3 2 2]
更平衡,可以得到7
。
类似题目: