USACO analysis
Jczeng |
18 Nov 2020
报告错误
如果你发现该网页中存在错误/显示异常，可以从以下两种方式向我们报告错误，我们会尽快修复：
- 使用 CS Club 网站错误 为主题，附上错误截图或描述及网址后发送邮件到 286988023@qq.com
- 在我们的网站代码仓库中创建一个 issue 并在 issue 中描述问题 点击链接前往Github仓库
problem2. Snow Boots
题目大意：
- 给定N（2≤N≤250）个地砖以及它们的积雪厚度，其中第一个和最后一个地砖的厚度是0；
- 给定装有B（2≤B≤250）对靴子的queue，每对的第一个数字为当前靴子可度过最深厚度，第二个为最长路程；
- 每过一个地砖，必须使用可s用的靴子，届时它的耐久减一；
- 并且可以为了使用下一个靴子而丢掉当前靴子；
- 问在度过所有地砖的情况下，可以的丢掉靴子的最少数量。
题目分析：
- 这题NB的上限特别少，所以可以直接使用完全搜索；
- 没经过一个地砖，会有B种情况；
- 因为只要达到目的后，直接弹出丢掉靴子数量而非路径方法，所以这题很适合用深度优先搜索来暴力枚举。
题目思路：
- 从第二个地砖开始遍历，深度搜索（地砖位置，靴子位置）；
- 每次dfs时，都把当前情况是否可行记录下来，实在不可行时便改变靴子，再次记录情况，直到丢掉所有靴子；
- 每遇到一个新的情况便记录，这样可以有效的大量地省去计算成本；
- 遍历完所有地砖或者靴子用完，改变前一个地砖的靴子位置，再次遍历；
- 若第一个地砖的所有靴子的情况都试过了，便可以结束遍历，返回queue 总长度减去靴子位置+1；
- 打印最大的返回值。
复杂度分析：
- 每次总共有O(N*B)种情况，每种情况需要遍历O(N+B)次，所以总的复杂度是O(N^2^B+NB^2^)。
