【bzoj3997】[TJOI2015]组合数学 Dilworth定理结论题+dp

时间:2022-01-07 00:50:09

题目描述

给出一个网格图,其中某些格子有财宝,每次从左上角出发,只能向下或右走。问至少走多少次才能将财宝捡完。此对此问题变形,假设每个格子中有好多财宝,而每一次经过一个格子至多只能捡走一块财宝,至少走多少次才能把财宝全部捡完。

输入

第一行为正整数T,代表数据组数。

每组数据第一行为正整数N,M代表网格图有N行M列,接下来N行每行M个非负整数,表示此格子中财宝数量,0代表没有

输出

输出一个整数,表示至少要走多少次。

样例输入

1
3 3
0 1 5
5 0 0
1 0 0

样例输出

10


题解

Dilworth定理结论题+dp

Dilworth定理:DAG最小路径覆盖=最长反链

其中:

最小路径覆盖指:选择最少的路径数,使得每个点在所有路径中出现至少1次。

最长反链指:选择最多的点,使得选定的点两两不能到达。

本题点带有权值(最小路径覆盖中至少出现v次,最长反链中计算的是权值和),也是一样的(可以看作是v个点)。

然后题目要求最小路径覆盖,转化为最长反链来求,而两两不能到达就相当于二维数点问题。

把原图按行翻转,就变为了:选择权值和最大的点,使得第i个点的横、纵坐标均大于第i-1个点。

设$f[i][j]$表示选择点$(i,j)$的最大权值和,那么状态转移方程为$f[i][j]=MAX_{k=0}^{i-1}MAX_{l=0}^{j-1}f[k][l]+a[i][j]$。可以使用二维前缀最大值优化这个过程,并且实际代码中可以不维护f数组。

时间复杂度$O(Tnm)$

#include <cstdio>
#include <cctype>
#include <algorithm>
#define N 1010
using namespace std;
int a[N][N] , f[N][N] , mx[N][N];
inline char nc()
{
static char buf[100000] , *p1 , *p2;
return p1 == p2 && (p2 = (p1 = buf) + fread(buf , 1 , 100000 , stdin) , p1 == p2) ? EOF : *p1 ++ ;
}
inline int read()
{
int ret = 0; char ch = nc();
while(!isdigit(ch)) ch = nc();
while(isdigit(ch)) ret = ((ret + (ret << 2)) << 1) + (ch ^ '0') , ch = nc();
return ret;
}
int main()
{
int T = read();
while(T -- )
{
int n = read() , m = read() , i , j;
for(i = n ; i ; i -- )
for(j = 1 ; j <= m ; j ++ )
a[i][j] = read() , f[i][j] = mx[i][j] = 0;
for(i = 1 ; i <= n ; i ++ )
for(j = 1 ; j <= m ; j ++ )
mx[i][j] = max(mx[i - 1][j - 1] + a[i][j] , max(mx[i - 1][j] , mx[i][j - 1]));
printf("%d\n" , mx[n][m]);
}
return 0;
}