简单写一下我遇到的坑点
查看原帖
简单写一下我遇到的坑点
823144
dkdk楼主2023/11/17 15:50

坑点1

注意任何时候都不要到高度为0,即我们永远不考虑0这样的高度。

坑点2

先计算第 i−1i - 1 列到第ii列只飞一次的情况(01背包),然后再计算可以飞大于两次的情况(完全背包)。01背包和完全背包分两次循环进行且不考虑管子,这两次循环结束后再判断是否被管子挡住。

如果在01背包做完后判断是否被管子挡住,会减小掉一些本来其实是可以飞过管子的情况,只是01背包暂时让它只飞一次且又恰好飞一次的位置被管子挡住了,因此不能在01背包做完后立马判断是否被管子挡住。

坑点3

在01背包和完全背包做完后再进行下降操作。因为题目说了要么这一单位时间是向上飞,要么是下降。而上升和下降一起处理可能会导致下降了的位置后续又向上飞了,不符合题意。

坑点4

有可能第 i−1i - 1 列飞过来的时候实际上是超过了最大高度mm的,所以这种越界情况要单独处理。

2023/11/17 15:50
加载中...