bzoj 3997 组合数学

Posted on | Views:

$Dilworth$ 定理.

图是一张 $DAG$ ,根据 $Dilworth$ 定理,它的最小链覆盖数就等于最长反链长度.

一条反链中的任意两点间都不存在边,所以一定是从左下到右上的一条链.

设 $f(i,j)$ 表示用了以 $(i,j)$ 为右上角的矩阵中的点,最长反链的长度.

从左下到右上进行 $dp$ 即可.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
//%std
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int MAXN=1e3+10;
int n,m,val[MAXN][MAXN];
ll f[MAXN][MAXN];
int main()
{
	int T=read();
	while(T--)
	{
		n=read(),m=read();
		for(int i=1;i<=n;++i)
			for(int j=1;j<=m;++j)
				val[i][j]=read();
		memset(f,0,sizeof f);
		for(int i=n;i>=1;--i)
			for(int j=1;j<=m;++j)
				{
					f[i][j]=0;
					f[i][j]=max(f[i][j],f[i+1][j]);
					f[i][j]=max(f[i][j],f[i][j-1]);
					f[i][j]=max(f[i][j],f[i+1][j-1]+val[i][j]);
				}
		printf("%lld\n",f[1][m]);
	}
	return 0;
}