内容
(Dilworth)定理是定义在偏序集上的。所谓偏序集，就是对于一个集合(A)，给定比较关系(p)（如(leq,ge)等），若其满足以下三个条件，则(p)和(A)被称为一个偏序集：
- 自反性：(a p a)
- 反对称性：若(a p b,b p a)，那么(a=b)
- 传递性：若(a p b,b p c)，则(a p c)
我们定义：
- 链：指一个集合(Ssubseteq A)，它的任意两个元素都可比。（可以看成是(DAG)上的一条路径上的一些元素，这些元素可能只是这条路径上不连续的一部分）
- 反链：指一个集合(S'subseteq A)，它的任意两个元素都不可比。（这个集合里的任何两个元素无法联通）
那么有
- 对于一个偏序集，其最少反链划分数等于其最大链的大小。
- 对于一个偏序集，其最少链划分数（指选出最少的链(可以重复)使得每个点都在至少一条链中）等于其最大反链的大小。
- (DAG)的最小链覆盖等于最大点独立集（最大点独立集指最大的集合使集合中任意两点不可达）
应用
在本题中，将每个格子拆为其财宝个数个元素，我们定义(a p b)指元素(a)在网格图中可以到达(b)。注意，同一格子中的元素是不能互相到达的（一次只能拿一个）
自然地，链就可以表示从左上角到右下角的一条路径，反链则是从右上角到左下角。
设(dp_{i,j})为以((i,j))为左下角的矩形中的最长反链长（这就是答案），那么
[dp_{i,j}=max{dp_{i-1,j},dp_{i,j+1},{dp_{i-1,j+1}+a_{i,j}}}
]
前两个是继承关系（矩形的并），后一个是包含((i,j))的最长反链长，因为((i,j))和((i-1, j-1))在一个反链。
代码：
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int t, n, m, a[1005][1005];
ll dp[1005][1005];
int read()
{
int x = 0, fl = 1; char ch = getchar();
while (ch < '0' || ch > '9') { if (ch == '-') fl = -1; ch = getchar();}
while (ch >= '0' && ch <= '9') {x = x * 10ll + ch - '0'; ch = getchar();}
return x * fl;
}
int main()
{
t = read();
while (t -- )
{
n = read(), m = read();
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
a[i][j] = read();
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] + a[i][j], max(dp[i - 1][j], dp[i][j + 1]));
printf("%lld
", dp[n][1]);
}
return 0;
}