开始时间：2025/12/20 10:33
额几天时间还算是比较充裕的吧。
先安排一下做什么吧？
1.复习剪枝DFS
2.完成老师布置的课后作业
3.总结一下周一到周五的学习
*4.（附加项）完成5题6级题目
先复习昨天没有复习完（或者说刚开了个头）的剪枝DFS。
依旧装箱问题。
看一眼老师给的一个总结。
上周课程的主题是：【最优性剪枝】，知识点如下：
核心思想：当前代价已经 ≥ 已知最优答案 → 不可能更优 → 直接剪掉。
用途：解决最小值类搜索（TSP、小猫爬山、最短路径、装箱问题）。
要求：代价必须单调递增，往下走只会更差。
⭐ 重点
1. 要有当前最优解作为“上界”（best）。
2. 当前代价 >= best 就剪。
⭐ 难点
1. 怎么尽早拿到一个上界（排序或贪心）。
2. 怎么估计剩余最小代价（lower bound）。
⭐易错点
1. 写成 > 而不是 >=。
2. 忘记回溯导致判断错误。
感觉对这套逻辑还不是很熟悉，打算先去看看别的在前面的题目，有没有更容易理解的。
应该是这个链接描述
啊啊啊我突然想去做拿到我没做出来的记搜的紫色神奇题目欸。
两个人饲养了N只小猫，花钱让他们做索道下山。
索道上的缆车最大承重量是W，N只小猫的重量分别是C1,C2,CN。
当然，每辆缆车上的小猫的重量之和不能超过W。
一辆缆车一美元。
所以他们想知道，最少需要付多少美元才能使所有小猫都坐上缆车。
好像不难，也好理解。
那么直接开始搓代码吧！
琢磨了好长时间，然后超时了。
怎么会，我明明加优化了啊啊啊。
先放一下代码吧：
那么如何进行进一步的优化呢？
1.使用排序/贪心尽早拿到一个上界
试试看吧。
额使用此神秘代码喜获37pts，剩下的从TLE变成了WA。
我研究一下。
好烦，我改了好几版，都出问题。
怎么回事
关键是它还不是T，也没有测试数据可以下。
我燃尽了
就这样吧
看题解去了
好吧其实我打算再看看。
但是我真的觉得我求的最小值没什么问题啊。
为什么会错啊
欸等一下，是不是我的DFS错了？
好吧我DFS好像确实写错了。
我改改吧。
去吃饭。
去喝酸奶。
去睡觉。
3：30了 我c
继续写。
为什么会错啊啊啊啊.
我尽我所能。
我去看题解。
算了。
我再想想。
我想不出来。
我去看题解。
我看完了。
大部分题解的思路是把猫塞进车里。
我觉得这种思路没什么问题。
但为什么我的思路就是错的。
为什么呢？
我想是因为。
我不知道。
我过了。
放一下代码吧：
额我讲一下吧，是这样的：
这道题就是一个非常典型的你的DFS构造会大大改变你的DFS树的形态和最终的运行时间。
我一开始的做法，思路非常不清楚。
大概的轮廓是，对于每一辆车，我都思考一下每一只猫能不能放进去。
放不进去，我就新开一辆出来。
那么，我不仅在DFS的过程中，暴力枚举了车的数量，我还没举了猫是如何放进去的。
其实就是有一种两种都枚举，思路非常不清楚的感觉，显得写题的人类是一个**。
所以就算做了再多的优化，它的本质超时会非常非常的严重。
暴力之间亦分上下的。
100pts的那个代码，它赢在了哪路呢？
看似都是一个循环的事儿，非常具有迷惑性。
但本质上就是不一样。
因为递归的次数是完全不一样的。
100的代码，它仅仅只是枚举了当前的这只猫放在哪里。
但是（最多）只有37的代码，在每次DFS里都枚举了每只猫的去向：
能塞进当前的车里的，就塞，然后下一轮。
不能塞进车里的，就新开一辆。
这种方法，不仅会导致已经在车里的猫被重复便利，还会导致
有一些情况需要很多次才能遍历到。
本质是非常非常暴力的。
我再想想怎么描述。我还是觉得描述的不清楚。
放猫的过程，有无数种可能，无数种形态，最初的解法，
就是把每一种形态每一种可能都过一遍。
这个可能的数量无限大。
那么思考，第一种和第二种的区别在哪里？
第一种，它的无限种可能在一开始就会全部都进行出来，导致时间复杂度爆炸。
额还是有点抽象。
这两个代码给我的感觉类似于这样：
一个很慌乱的做出了很多很多选择，然后大部分都是错的。
一个有条理地做出了精炼的选择，最后想正确答案步步逼近。
差不多了，不说这道题了，现在已经17:39了，再在这道题目上耗时间，我后面的事情很多来不及。
试试看这个链接描述
好像差不多欸。
双倍经验！
啊下一题吧。
链接描述
这道题跟前面两题不太一样的。
没有“价值”一说，n<=30，如何进行优化？
啊不管了，先来一发暴力！
啊拿了40
情理之中，意料之内。
如何优化？
加了点东西，拿了60pts.
但是接下来我真的不知道怎么优化了。
qwq给题目卖个萌
放过我吧球球了
我真不会优化。
但我会看题解。
没关系。
一切都会好起来的。
明天考试考不了第一怎么办？
月考有塌方怎么办？
……
再说吧。
去吃晚饭吧。
我懂了！
在进行DFS的时候，每次的x一般都直接作为下标。
而不是作为“进行了几次递归”的一个变量。
！
赋值语句要写在return前面。
过了，放个代码。
下一题。
链接描述
这道题跟最优性剪枝有什么关系吗？
试试看打一发暴力吧。
等等……我好像有思路了。
要注意有没有特殊可能。
额暴力打完了，拿了30pts。
我不太喜欢做剪枝。
真的。
放一下暴力代码
等等……我觉得好像不是这么写的。
我改一下。
洛谷评测机炸了……玩我呢？
好吧。拿了80pts。但是我真的不太会优化……
依旧展示代码。
