学习了\(\rm Dilworth\)定理，即偏序集的最小全序集划分等于最大反链长度
定理的内容看起来非常自闭，偏序集、全序集和反链都是个啥
偏序集其实非常常见，经典的二维偏序、三维偏序其实就是最基本的偏序关系，比如说一个二元组集合\(A\)，对于\((x_1,y_1),(x_2,y_2)\in A\)，当\(x_1\leq x_2,y_1\leq y_2\)时我们称\((x_1,y_1)\leq (x_2,y_2)\)，则\((A,\leq )\)为一个偏序集
如果存在\(x_1\leq x_2,y_1>y_2\)，我们就无法在\((A,\leq)\)这个偏序集中定义\((x_1,y_1),(x_2,y_2)\)的大小关系，那么就称\((x_1,y_1),(x_2,y_2)\)在\((A,\leq)\)中不可比
全序集是偏序集的一个子集，如果\(B\subseteq A\)，且\(\forall (x_1,y_1),(x_2,y_2)\in B\)，存在\((x_1,y_1)\leq (x_2,y_2)\)或\((x_2,y_2)\leq (x_1,y_1)\)，即两两元素可比，则称\(B\)为\(A\)的一个全序集
如果对于\(A\)的一个子集，其中元素两两不可比，则称该子集为一个反链
于是这个定理通俗理解一下大概就是，把一个偏序集划分成若干个两两可比的集合，这个划分数的最小值等于最大的两两不可比的子集的元素个数。
这个定理还可以推广到\(\rm DAG\)上，即\(\rm DAG\)的最小路径划分等于最大独立集的大小
这也非常好理解，我们可以把\(\rm DAG\)的边看成偏序集的大小关系，最小路径划分等价于选出一些全序集，而最大独立集保证两两点不可达，即是一个最大反链。
对于这道题我们可以大致理解为如果两个格子\((a,b),(c,d)\)存在\(a\leq c,b\leq d\)，我们就称两个格子存在偏序关系。
不难发现由于我们只能向下或向右走，我们一次走过的点一定是一个全序集，而我们要求的就是全序集的最小划分数。
所以我们求一个最大反链长度即可。
由于我们经过一个点一次只能使得这个点的点权减一，所以我们把每个点视为点权个点。搞一个从左上往右下转移的dp即可。
代码
#include<bits/stdc++.h>
#define re register
#define LL long long
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
inline int read() {
char c=getchar();int x=0;while(c<'0'||c>'9') c=getchar();
while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();return x;
}
const int maxn=1e3+5;
int T,n,m,a[maxn][maxn];
LL dp[maxn][maxn];
int main() {
T=read();
while(T--) {
n=read(),m=read();
for(re int i=1;i<=n;i++)
for(re int j=1;j<=m;j++) a[i][j]=read(),dp[i][j]=a[i][j];
for(re int i=1;i<=n;i++)
for(re int j=m;j;--j) {
dp[i][j]=dp[i-1][j+1]+a[i][j];
dp[i][j]=max(dp[i][j],dp[i-1][j]);
dp[i][j]=max(dp[i][j],dp[i][j+1]);
}
LL ans=0;
for(re int i=1;i<=n;i++)
for(re int j=1;j<=m;j++) ans=max(ans,dp[i][j]);
printf("%lld\n",ans);
}
return 0;
}