P16772 [GKS 2020 #G] Maximum Coins

Mike 有一个 $N$ 行 $N$ 列的方阵。单元格 $(i, j)$ 表示第 $i$ 行第 $j$ 列的格子。单元格 $(1, 1)$ 表示矩阵的左上角。每个格子中有一定数量的硬币，Mike 只有访问该格子时才能收集它们。$C_{i, j}$ 表示第 $i$ 行第 $j$ 列格子中的硬币数。从格子 $(i, j)$ 出发，Mike 可以决定移动到 $(i+1, j+1)$ 或 $(i-1, j-1)$，只要该格子仍在矩阵边界内且尚未被访问过。他可以选择从任意格子开始，并在任意时刻停止。Mike 希望最大化他能收集到的硬币总数。请帮助他确定能收集到的最大硬币数。

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。每个测试用例的第一行包含一个整数 $N$。接下来的 $N$ 行，每行包含 $N$ 个整数。第 $i$ 行的第 $j$ 个整数表示单元格 $(i, j)$ 中的硬币数 $C_{i, j}$。

对于每个测试用例，输出一行，格式为 `Case #x: y`，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是 Mike 能收集到的最大硬币数。

在样例 #1 中，如果 Mike 沿着路径 $(1,1) \to (2,2) \to (3,3)$ 行走，他最多可以收集到 $14$ 枚硬币。 在样例 #2 中，如果 Mike 沿着路径 $(2,3) \to (3,4)$ 行走，他最多可以收集到 $9$ 枚硬币。 ### 限制条件 $1 \le T \le 100$。 $0 \le C_{i, j} \le 10^7$。 **测试集 1** $1 \le N \le 100$。 **测试集 2** 最多 $10$ 个测试用例满足 $1 \le N \le 10^3$。 其余所有测试用例满足 $1 \le N \le 100$。 翻译由 DeepSeek V4 Pro 完成