啊啊啊啊
2025-12-19 23:05:30
发布于：上海
额今天来做一下老师给的复习题（虽然，我应该先复习剪纸，但是，我有点急）
今天已经很晚了，明天多练点吧。
开始时间：2025/12/19 21:48
哇塞蓝题，这么牛逼
链接描述
我看看。
哇塞还不保证一定通过。
乔治有一些同样长的小木棍，他将这些木棍砍成len<=50的随意几段。
他想把小木棍拼接成原来的样子。但是却忘了自己原来有多少跟木棍和它们的长度。
现在给出每段小木棍的长度，变成帮他找出原始木棍的最小可能长度。
啊啊啊剪枝DFS吧。
我想想。
我的初步想法是从max{len[i]}到len[1]+...+len[n]进行一个for循环。
试试看。
可是如何去进行DFS呢？
写好了，能拿21pts。看看怎么修改吧。
这个应该不是记搜，记搜的n不会只有65.
但是如何去优化呢?
那就刚好借着这个机会复习一下剪枝DFS吧。
啊啊啊后天我要打ABC。
其实我不爱打比赛。非常讨厌。非常折磨。
深搜的剪枝有很多种，但是由于效率问题，就只介绍两个（明天有时间继续吧。
1.可行性剪枝
在搜索过程中，及时对当前状态进行检查，如果分支已经无法到达递归边界，则直接进行回溯。
比如说，小木棍一题中，当前我想确定我的i是否可能满足条件，我就去mod一下我的sum2。
应为一定要能整除。
再比如说，我现在想要求取最小值，但是我本次DFS中的可能最小值>我已经算出的最小值，那么直接return即可。
试试看实现在小木棍一题中吧。蓝题啊。
没那么好做嘞。
写这种题，感觉就像长跑，精神已经到极限了，还要再逼自己一把。
观我旧往。
啊啊啊改完了。获得了27pts.怎么这么鸡肋。我还以为能过很多呢！
那就继续看看下一种优化方式吧。
2.最优性剪枝。
我不太懂这个是怎么做的。
我看了两种解答：
1.在最优化问题的搜索过程中，如果当前花费的代价已经超过当前搜到的最优解，那么无论采取多么优秀的策略到达递归边界，都不可能更新答案。此时可以停止对当前分支的搜索，执行递回溯。
2.当前代价已经 ≥ 已知最优答案 → 不可能更优 → 直接剪掉。
第二种说法，类似于甘冈可行性剪枝的第二种。
那我们看看例题吧。
链接描述
有一个箱子容积为V，同时有n个物品，每个物品有一个体积。
现在从n个物品中，人去若干个装入箱内，使箱子的剩余空间尽量小。
噢噢噢噢对了，顺便再补充一个比较小的点：
3.优化搜索顺序
对于每一个问题，你一不同的顺序去进行一个枚举，它所构建出来的搜索树是相差甚远的。
有的时候，你可以尝试通过观察这颗搜索树的具体形态，像一个园丁那样去给出这棵树最完美，最精炼的形态。
比如说，NOI1999生日蛋糕这一题中，你就可以去选择从大到小进行枚举。
包括大部分问题，你将其进行排序后，从大到小遍历，你的时间复杂度从魔种程度上来说就会减小很多。
为什么？使用大数开头，可以为你迅速地清扫很多一些不可行方案。如果你从小到大遍历，那么可能要等到很后面，你才会发现欸这条路好像行不通啊。
所以说，箱子这题，你可以那个什么排个序。
（额其实我也不确定排序一定有用啊）
太累了，不写了。
结束时间：2025/12/19 23：04
这里空空如也
有帮助，赞一个