题目
题解
如果把一条路径看成一条链，把这个网格图看成一个$DAG$，这个题就是求$DAG$的最小链覆盖（链的值为覆盖点的最大值）
一看到链覆盖我就想到网络流，一想到网络流我就点开了……
嗯嗯嗯好的我知道了要做一遍传递闭包把可以相交的最小路径覆盖转化为了路径不能相交的最小路径覆盖然后跑个网络流就好啦果然很简单嘛
可以转换一下思路，有定理：
最小链覆盖=最大独立点集
一看到独立点集我就想到网络流……停)
发现这个图点$(x,y)$和$(x-1,y+1)$肯定是在两个点集中的，而且$(x,y)$可能和$(x-1,y),(x,y+1)$在同一个点集中
设$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})$
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<algorithm>
# define LL long long
using namespace std;
const int N=1e3+5;
int T,n,m;
int a[N][N];
LL f[N][N];
int read()
{
int x(0);
char ch=getchar();
for(;!isdigit(ch);ch=getchar());
for(;isdigit(ch);x=x*10+ch-48,ch=getchar());
return x;
}
int main()
{
T=read();
while(T--)
{
n=read(),m=read();
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
a[i][j]=read(),f[i][j]=0;
for(int i=1;i<=n;++i)
for(int j=m;j>=1;--j)
f[i][j]=f[i-1][j+1]+a[i][j],f[i][j]=max(f[i][j],max(f[i-1][j],f[i][j+1]));
printf("%lld\n",f[n][1]);
}
return 0;
}
