Description：

一个网格图，从左上角出发，只能往右或往下走，最后到达右下角，格子有最低经过次数，问最少走几次。

$1\leqslant n\leqslant 10^3$

Solution：

首先把每个格子拆成最低经过次数这么多个点，然后就变成了一个可重复路径覆盖，由 $Dliworth$ 定理得最小链覆盖 $=$ 最长反链长度，所以就是求一个从右上角出发，每次只能往左下方走，不能往左或往下，每次到一个格子就加上这个点的权值，这个可以 $DP$ ，然后二维前缀和优化一下。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 1010

int val[MAXN][MAXN];

int f[MAXN][MAXN];

void work()

{

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

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

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

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

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

	{

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

		{

			f[i][j] = f[i - 1][j - 1] + val[i][j];

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

		}

	}

	cout << f[n][m] << endl;

	return;

}

int main()

{

	int testcases;

	scanf("%d",&testcases);

	while(testcases--)work();

	return 0;

}