放个贪心做法

对于每个格子，优先从上面的步数转移，上面步数不够，再从左边的步数转移，左边加上面的步数都不够，就ans+即可

code

bool M1;
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define deb(x) cerr<<"l: "<<__LINE__<<"  "<<#x<<"="<<x<<'\n'
#define look_memory cerr<<abs(&M2-&M1)/1024.0/1024<<"MB\n"

namespace syr
{
	const ll N = 1010;
	const ll M = 0x3f3f3f3f;
	ll t, n, m, x, tot, ans;
	ll res[N], s[N];
	void work()
	{
		cin>>t;
		while (t--) {
			ans = 0;
			memset(res, 0, sizeof(res));
			cin>>n>>m;
			for (ll i=1; i<=n; i++) {
				tot = 1, s[1] = 0, res[0] = M;
				for (ll j=1; j<=m; j++) {
					cin>>x;
					if (x>res[j]) {
						ll d = x-res[j];
						while (res[s[tot]]<d) {
							d -= res[s[tot]];
							res[s[tot]] = 0;
							tot--;
						}
						res[s[tot]] -= d;
						res[j] = x;
					}
					s[++tot] = j;
				}
				ans += M-res[0];
			}
			cout<<ans<<'\n';
		}
	}
}

bool M2;

int main()
{
	cin.tie(0)->sync_with_stdio(0);
	look_memory;
	syr::work();
	return 0;
}

原题：P3974 [TJOI2015] 组合数学

Dilworth定理

首先这个东西是什么

为了便于理解，我这里会把链说为正链

他有两个结论

1.最长反链长度等于最小的正链覆盖数

2.最长正链长度等于最小的反链覆盖数

(对于这个东西的证明，大家可以看一下lzd大佬的证明，我这里就不放证明了)

在偏序集内，我们定义一种二元关系$R$

若一个集合内的所有元素都互相满足关系$R$则称这个集合为正链，他的元素个数为正链长度

同样的，若所有元素都互相不满足$R$,则称这个集合为反链，他的元素个数为反链长度

做法

这个题我们可以看出他的R就是

upd:这里$R$是关于两个点之间的二元关系

$R((i,j),(i-1,j)) = 1$

$R((i,j),(i,j-1)) = 1$

然后这个题让我们求最小的正链覆盖数，这个是不好求的，所以我们转化为最长反链长度。

对于每个点$(i,j)$我们把他拆成$a[i][j]$个相同的点，他们之间相互独立，所以可以放到同一个反链中，所以他的权值就是$a[i][j]$

这样我们就可以做了

我们定义$f[i][j]$为从$(1,m)$到$(i,j)$之间的最长反链长度

不难发现我们可以判断选或者不选这个点

$f[i][j] = max(f[i-1][j],f[i][j-1],f[i-1][j+1]+a[i][j])$

然后答案就是$f[n][1]$

这个题就做完了

code

#include <bits/stdc++.h>
using namespace std;

const long long N = 1e3 + 10;

long long n, m, a[N][N], f[N][N];

void read() {
	cin >> n >> m;
	for(long long i = 1; i <= n; i++) {
		for(long long j = 1; j <= m; j++) {
			cin >> a[i][j];
		}
	}
}

void compute() {
	memset(f,0,sizeof(f));
	for(long long i = 1; i <= n; i++) {
		for(long long j = m; j >= 1; j--) {
			f[i][j] = max(f[i-1][j+1]+a[i][j],max(f[i-1][j],f[i][j+1]));
		}
	}
	cout << f[n][1] << '\n';
}

int main() {
	int t;
	cin >> t;
	while(t--) {
		read();
		compute();
	}
	return 0;
}

Dilworth定理证明

证明：最大正链长度 = 最少反链覆盖

然后最大反链长度 = 最少正链覆盖，反之亦然。

我来证明第一个。

假设最大正链长度为 $l$，最少反链覆盖为 $r$。

而且序列不限于大小关系，只要是满足：这种关系就行，假设这种运算符为R。这个叫偏序

aRa（自反性）

若 aRb,bRa，则有 a=b（反对称性）

若 aRb,bRc，则有 aRc（传递性）

证明 $l \le r$：

这个最长正链里面有 $l$ 个元素，而反链就是正不了一点的链，所以这 $l$ 个元素必须在 $l$ 个反链里出现，所以 $l\le r$。

证明 $r \le l$：

你现在有很多正链，如果按大小顺序依次取出，那么每次取出的都是反链（否则就可以一起形成正链了），然后这些反链最多也就 $l$，所以 $r\le l$。

然后这道题怎么做

你要从左上角走到右下角，然后他有一种很明显的偏序关系，就是

右下的一定比左上的点更右下

然后直接找出最大的反链就行了。

因为只要是走到了，你一定会把最大的走完，所以这就是一个最小正链覆盖，所以只需要求出最大反链。

#include<bits/stdc++.h>
#define int long long

using namespace std;
int T,n,m;
int a[1005][1005];
int dp[1005][1005];
signed main() {
//	freopen("in.txt","r",stdin);
	cin>>T;
	while(T--) {
		cin>>n>>m;
		for(int i=1; i<=n; ++i) {
			for(int j=1; j<=m; ++j) {
				cin>>a[n-i+1][j];
			}
		}
		memset(dp,0,sizeof dp);
		for(int i=1;i<=n;++i){
			for(int j=1;j<=m;++j){
				dp[i][j]=max(dp[i-1][j-1]+a[i][j],max(dp[i-1][j],dp[i][j-1]));
			}
		}
		cout<<dp[n][m]<<"\n";
	}
	return 0;
}