P14996 [Nordic OI 2020] Bricks

Josefine 正在玩一个类似俄罗斯方块的游戏，名为 bricks。游戏在一个 $6$ 列 $\times$ $8$ 行的矩形网格中进行。一个砖块占据网格中一个 $1 \times 1$ 的格子。初始时网格为空。一个砖块图案是一个矩形，其中部分格子被砖块填充，其余部分是空气。以下是一个 $4 \times 3$ 砖块图案的例子，其中 `#` 代表砖块，`_` 代表空气： ``` #_## ##__ #__# ``` 游戏进行 $N$ 轮。在每一轮中，玩家会看到一个砖块图案，她必须决定将其从网格顶部（水平方向上）何处落下。当落下砖块图案时，每个砖块将独立地沿垂直线下落，并落在网格底部或另一个砖块（来自同一图案或之前轮次）的正上方。由于砖块独立下落，之后在每一列中砖块之间不会有空隙（这与俄罗斯方块不同）。在落下砖块图案之前，玩家可以将其旋转 0、90、180 或 270 度。砖块图案必须被落下，使得所有砖块都落在网格内。 在每轮结束时，网格中所有拥有至少 3 个砖块的列将发生坍塌，这些砖块随之从网格中移除。第 $i$ 轮有一个对应的轮次分数 $s_i$。设 $b_i$ 为该轮中坍塌的砖块数，则玩家在该轮获得 $b_i \cdot s_i$ 分。 游戏的目标是最大化所有轮次的总得分（即最大化 $\sum_{i=1}^{N} b_i s_i$）。请帮助 Josefine，编写一个程序，在给定这 $N$ 个砖块图案和轮次分数的情况下，计算出可能获得的最大分数。

- 第一行：轮数 $N$（$1 \leq N \leq 300$）。 - 对于每一轮： - 下一行：整数 $w_i$, $h_i$, $s_i$，其中 $w_i \times h_i$ 是第 $i$ 个砖块图案的尺寸，$s_i$ 是轮次分数（$1 \leq w_h, h_i \leq 6$ 且 $0 \leq s_i \leq 10000$）。 - 接下来的 $h_i$ 行：表示砖块图案，为一个由 `#` 和 `_` 组成的 $w_i \times h_i$ 矩形，其中 `#` 代表砖块，`_` 代表空气。（该矩形始终是能覆盖图案中所有砖块的最小可能矩形。）

- 第一行：可能获得的最大分数。

如果我们简单地将第一个砖块图案不旋转并尽可能向左落下，我们得到： ``` ______ ______ ______ ______ ______ ______ #_____ ##____ ``` 然后，我们将第二个砖块图案逆时针旋转 90 度，并尽可能向左落下，我们得到：（用 X 标记坍塌的砖块——它们将在下一轮开始前消失）。 ``` ______ ______ ______ ______ X_____ X_____ X#____ X#____ ``` 由于第二轮轮次分数是 4，我们从这一轮获得 $4 \cdot 4 = 16$ 分。最后，我们将最后一个砖块图案旋转 180 度，并将其落在从左数第二靠左的位置，我们得到： ``` ______ ______ ______ ______ _X____ _X_X__ _X_X__ _X#X__ ``` 最后一轮轮次分数是 $2$，因此我们在这一轮获得 $2\cdot 7 = 14$ 分。总共我们得到 $0 + 16 + 14 = 30$ 分。这是最优解。 ### 评分细则 你的解法将通过子任务进行测试。要获得一个子任务的分数，你需要通过该子任务中的所有测试用例。 | # | 分数 | 限制条件 | |:-:|:-:|:-:| | 1 | 30 | $n \leq 5$ | | 2 | 70 | 无额外限制。 | 翻译由 DeepSeek V3 完成