放个贪心做法

对于每个格子，优先从上面的步数转移，上面步数不够，再从左边的步数转移，左边加上面的步数都不够，就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] 组合数学