题意

\(N \times M\)的网格，一开始在\((1, 1)\)每次可以向下和向右走，每经过一个有数字的点最多能将数字减1，最终走到\((N, M)\)。问至少要走多少次才能将数字全部变为\(0\)。（\(N, M<=1000, a_{i, j}<=10^6\)）

分析

结论题QAQ，不会证明...

题解

设\(d(i, j)\)

\(d(i, j) = max( d(i-1, j), d(i, j+1), d(i-1, j+1) ) + a[i, j]\)

答案是\(d(n, 1)\)

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

ll d[1005][1005];

int main() {

	int T;

	scanf("%d", &T);

	while(T--) {

		int n, m;

		scanf("%d%d", &n, &m);

		for(int i=1; i<=n; ++i) {

			for(int j=1; j<=m; ++j) {

				scanf("%lld", &d[i][j]);

			}

		}

		for(int i=1; i<=n; ++i) {

			for(int j=m; j>=1; --j) {

				d[i][j]=max(d[i][j]+d[i-1][j+1], max(d[i][j+1], d[i-1][j]));

			}

		}

		printf("%lld\n", d[n][1]);

	}

	return 0;

}