题意简述

题目链接

Vijos ETO P1002

题目描述

有一个 \(r\times c\) 的矩阵 \(a\)，矩阵上的每个点都有一个对应的数值，经过这个点就可以取得对应的数值。

现在位于位置 \((1,1)\)，只能往右或者往下走，终点为 \((r,c)\)。

最大化取得的数值。

题目有多组测试数据。

样例输入

2
2 2
1 1
3 4
2 3
2 3 4
1 6 5

样例输出

8
16

思路分析

这是一道经典的 数字三角形模型 的题目，仅将 数字三角形 三角形改为矩形。

状态表示

对于矩阵中的点 \((i,j)\)，定义状态 \(f_{i,j}\)。

为什么是这样定义呢？很遗憾，这个问题没有通解（ ~~这个是 NP 完全问题~~ ），但是只要做多了题，就能够想出来。最后在总结数字三角形模型的时候，笔者会对这种方法做一种解释。

集合

由于路径是 \((1,1)\to(i,j)\)，而且题目中要求的是取得的数值，所以集合的定义就呼之欲出了。

集合： 所有从 \((1,1)\) 到 \((i,j)\) 的所有路径。

属性

题目要求 最大化取得的数值，所以属性当然就是 \(\max\) 了。

说得具体一点，是路径上所有取得的数值之和的 \(\max\)。

状态计算

最后一个不同的点是什么？就是从哪个点转移过来。

从上图可以看出 \((i,j)\) 只能由 \((i-1,j)\) 和 \((i,j-1)\) 转移而来，所以可以将集合分为两部分：

左边的集合如何计算？我们可以将其分为两步： \((1,1)\to(i-1,j)\to(i,j)\)。

其中，\((1,1)\to(i-1,j)\) 有许多路径，但是它们的描述是： 所有从 \((1,1)\) 到 \((i-1,j)\) 的所有路径。回顾上面的状态表示，可以发现，这个描述不正恰好是 \(f(i-1,j)\) 的定义吗？所以 \((1,1)\to(i-1,j)\) 就可以用 \(f_{i-1,j}\) 来表示了。

接下来是 \((i-1,j)\to(i,j)\)。这一步中，取得的数值增大了 \(a_{i,j}\)，所以最终的结果中就要加上这一数值。

综上所述，左边的集合可以这样计算：\(f_{i-1,j}+a_{i,j}\)。
同理，右边的集合的计算方法：\(f_{i,j-1}+a_{i,j}\)。

由于属性是 \(\max\)，所以状态转移方程显而易见：\[f_{i,j}=\max\{f_{i-1,j}+a_{i,j},f_{i,j-1}+a_{i,j}\}=\max\{f_{i-1,j},f_{i,j-1}\}+a_{i,j}\]

当然，这道题也可以直接感性理解来做。由于 \((i,j)\) 由 \((i-1,j)\) 和 \((i,j-1)\) 转移而来，而要最大化取得的数值，所以 \((i,j)\) 应该从 两个点中之前取得的数值（即 \(f_{i-1,j}\) 和 \(f_{i,j-1}\)）最大的点转移过来，保证这一步是最优的。

代码实现

实现细节

Q1：\(a\) 数组呢？

A1：因为 \(a\) 数组在读入后就再也没有用过，那么就可以直接用 \(f\) 数组来读入并且进行计算。相当于用 \(f\) 覆盖了 \(a\)。

---

Q2：为什么可以一边读入一边计算？

A2：因为 \(f_{i,j}\) 仅与 \(f_{i-1,j}\) 和 \(f_{i,j-1}\) 相关，而循环顺序是 \(i,j\) 均从小到大枚举，所以计算 \(f_{i,j}\) 时 \(f_{i-1,j},f_{i,j-1}\) 都已经更新过了，可以直接拿来使用。

---

Q3：为什么不用考虑边界条件？

A3：因为题目中保证了 \(a\) 中的数字均为正整数，而全局变量中边界的值都是 \(0\)，非边界的值更新过后必然大于 \(0\)，所以边界的值时不会被 max() 选中。当然，\((1,1)\) 的时候两个前驱值都是 \(0\)，但是由于 \(f_{1,1}=a_{1,1}\)，所以这样写的话两个代码时等价的。

最终代码

#include <iostream>
const int MAX = 110;

int T, R, C;
int f[MAX][MAX];

int main() {
  for (std::cin >> T; T; --T) {
    std::cin >> R >> C;
    for (int i = 1; i <= R; ++i)
      for (int j = 1; j <= C; ++j)
        std::cin >> f[i][j], f[i][j] += std::max(f[i - 1][j], f[i][j - 1]);
        // 直接使用状态转移方程进行计算
    std::cout << f[R][C] << std::endl;
    // 根据定义，f[R][C] 就是所有从 (1,1) 到 (R,C) 的所有路径取得的数值的最大值，也就是答案了。
  }
  return 0;
}