既然题目叫《组合数学》，当然要用组合数学啦！

这题可以应用组合数学中的 Dilworth 定理，结合动态规划思想，求解最大独立集问题。题目给定一个权值矩阵，我们需要从中选取一些点，使得这些点两两不可达且权值和最大。

Dilworth 定理指出，在一个偏序集合中：

• 最大反链的大小等于最小链覆盖的大小。
• 同时，最大反链的大小也等于最大独立集的大小。

在本题中，我们的目标是构造一个最大独立集，即选择一组点，使得这些点之间没有直接的达到关系（以左下减右上的关系为标准）。为了解决该问题，我们可以使用动态规划。

我们定义 $dp[i][j]$ 表示从 $(1, m)$ 到 $(i, j)$ 的最大权值和，且 $(i, j)$ 不能和 $(i−1, j+1)$ 同时被选取。

所以，状态转移方程大体如下：

• 如果不选 $(i, j)$，我们考虑 $(i-1, j)$ 和 $(i, j+1)$ 的值。
• 如果选取 $(i, j)$，则将其对应的权值 $g[i][j]$ 加入。

因此，状态转移方程为：

$$dp[i][j] = \max(dp[i-1][j+1] + g[i][j], dp[i-1][j], dp[i][j+1])$$

Code

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;

long long dp[1005][1005];
long long g[1005][1005];

int main() 
{
	int t;
	cin >> t;
	while (t--) {
		int n, m;
		cin >> n >> m;

		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				cin >> g[i][j];
			}
		}

		memset(dp, 0, sizeof(dp));

		for (int i = 1; i <= n; i++) {
			for (int j = m; j >= 1; j--) {
				dp[i][j] = max(dp[i - 1][j + 1] + g[i][j], max(dp[i - 1][j], dp[i][j + 1]));
			}
		}

		cout << dp[n][1] << '\n';
	}

	return 0;
}