[TJOI2015]组合数学

洛谷题目链接
这道题的码量不大，代码没什么难度，但是思维难度会比较大。
注意，有T组数据，每次都需要初始化,并且需要开long long

---

解释

我们有一个神奇的定理叫做Dilworth定理。
即：最长反链=最小链覆盖=最大独立集。
这道题其实就是求最小链覆盖。
最小链覆盖：用最少的链让每一个点都在至少一个链中。
最长反链：即最长的反链。
反链：链中所有的点都是偏序关系。
偏序：非正序，在本题中只能向下和向右，所以向上和向左即为偏序。
最大独立集：最大的集合，其中相互两点无法到达。
至于为什么相等，证明很麻烦我不会，但是仔细想想是能理解的。

---

题解

我们在这个题中需要求出最长反链，我们用dp来求。
由于是反链，我们的\(f_{i,j}\)可以从\(f_{i-1,j}\)和\(f_{i,j+1}\)转移，如果是右上\(f_{i-1,j+1}\)到\(f_{i,j}\)我们就需要宝藏数次(因为一次只能取一个)，也就是：
\(f_{i,j}=max(f_{i-1,j},f_{i,j+1},f_{i-1,j+1}+a_{i,j})\)

---

标程

#include<bits/stdc++.h>
using namespace std;
const int MN=1010;
#define int long long
int T,n,m;
int a[MN][MN],dp[MN][MN];
void init(){memset(a,0,sizeof(a)),memset(dp,0,sizeof(dp));}
signed main(){
	//freopen("math.in","r",stdin);
	//freopen("math.out","w",stdout);
	scanf("%lld",&T);
	while(T--){
		init();
		scanf("%lld%lld",&n,&m);
		for(int i=1;i<=n;++i)for(int j=1;j<=m;++j)scanf("%lld",&a[i][j]);
		for(int i=1;i<=n;++i){
			for(int j=m;j>=1;--j){
				dp[i][j]=max(dp[i-1][j],max(dp[i][j+1],dp[i-1][j+1]+a[i][j]));
			}
		}
		printf("%lld\n",dp[n][1]);
	}
	return 0;
}