AT_utpc2021_g Matrix Compressor
题目描述
你有一个 $ H $ 行 $ W $ 列的矩阵，每个矩阵元素都是 $ 1 $ 到 $ 9 $ 之间的正整数，即 $ S_{i, j} $。
你可以按照任意顺序执行以下两种操作，总共可以进行 $ H + W - 2 $ 次：
1. **行操作**：选择两行相邻的行（第 $ i $ 行和第 $ i + 1 $ 行），获得这两行所有元素之和作为得分，然后将这两行压缩。具体操作是：用（如果有）第 $ i - 1 $ 行及之前的行、第 $ i $ 行和第 $ i + 1 $ 行的所有元素之和、（如果有）第 $ i + 2 $ 行及之后的行，按照这个顺序重新组成矩阵。此操作要求矩阵至少有两行。
2. **列操作**：选择两列相邻的列（第 $ j $ 列和第 $ j + 1 $ 列），获得这两列所有元素之和作为得分，然后将这两列合并。具体操作是：用（如果有）第 $ j - 1 $ 列及之前的列、第 $ j $ 列和第 $ j + 1 $ 列的元素之和、（如果有）第 $ j + 2 $ 列及之后的列，按照这个顺序重新组成矩阵。此操作要求矩阵至少有两列。
请计算通过上述操作可以获得的最大总分数。
输入格式
输入由标准输入给出，格式如下：
> $ H $ $ W $
> 在接下来的 $ H $ 行中，每行输入 $ W $ 个整数，表示矩阵的元素。
输出格式
输出可以获得的最大总分数。
说明/提示
- 所有输入均为整数
- $ 1 \le H, W \le 3000 $
- $ 1 \le S_{i, j} \le 9 $
### 部分分数
- 对于满足 $ 1 \le H, W \le 200 $ 的测试用例，若答案正确则可以得到 $ 30 $ 分。
### 示例说明
例如，按顺序选择第 $ 2, 3 $ 列、第 $ 2, 3 $ 行、第 $ 1, 2 $ 行和第 $ 1, 2 $ 列可以得到最大得分。依次计算这些操作后，得分为 $ 30 + 28 + 36 + 36 = 130 $。以下是矩阵变化过程：
$$
\begin{bmatrix}
3 & 1 & 4 \\
1 & 5 & 9 \\
2 & 6 & 5 \\
\end{bmatrix}
\to
\begin{bmatrix}
3 & 5 \\
1 & 14 \\
2 & 11 \\
\end{bmatrix}
\to
\begin{bmatrix}
3 & 5 \\
3 & 25 \\
\end{bmatrix}
\to
\begin{bmatrix}
6 & 30 \\
\end{bmatrix}
\to
\begin{bmatrix}
36 \\
\end{bmatrix}
$$
**本翻译由 AI 自动生成**