TJOI2015 组合数学
和组合数学有什么关系呢。。。
本题相当与求该图的最小链覆盖
由\(Dilworth\)定理:\(DAG\)的最小链覆盖=最大点独立集
最大点独立集对于本图来说就是左下到右上一条最长路。
然后dp一下
\(f[i][j]=max(max(f[i-1][j],f[i][j+1]),f[i-1][j+1]+g[i][j])\)
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N=1005;
int n,m,g[N][N],f[N][N],T;
int main() {
scanf("%d",&T);
while(T--) {
scanf("%d%d",&n,&m);
memset(f,0,sizeof f);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d",&g[i][j]);
for(int i=1;i<=n;i++)
for(int j=m;j;j--)
f[i][j]=max(max(f[i-1][j],f[i][j+1]),f[i-1][j+1]+g[i][j]);
cout<<f[n][1]<<endl;
}
return 0;
}