小编xas*_*hru的帖子

这是一个基于俄罗斯方块的谜题.在这个谜题中,我们将获得接下来将从顶部落下的n个片段的序列.我们的工作是在GameOver之前最大化得分.一般的俄罗斯方块没有多项式时间算法,但在这个难题中只允许I(直)四联体.虽然它不允许旋转它们.

所以这里是约束:

• 该板是W×H矩形
• 我们给出了下n个四联骨牌的序列
• 只允许我使用tetromino(水平或垂直)
• 不允许旋转
• 当行填满时,行会被清除
• 董事会最初是空的
• 每行清除1分.
• 当tetrominoes叠加到比赛场地的顶部时,游戏结束了.

找到可以获得的最高分数.

例:

8 x 6板.接下来的7个tetrominoes是[——,|,|,——,|,——,|]其中'——'表示水平我四氨基和|表示垂直我四氨基.

在这种情况下,最大可能得分是3使用以下策略('.'代表空板,'#'代表四氨基片的一部分).

Initially:
........
........
........
........
........
........
1st move:
........
........
........
........
........
####....
2nd Move:
........
........
.......#
.......#
.......#
####...#
3rd Move:
........
........
......##
......##
......##
####..##
4th Move:
........
........
......##
......##
####..##
####..##
5th Move:
........
........
.....###
.....###
####.###
####.###
6th Move:
........
........
.....### …