BZOJ3997 TJOI2015组合数学（动态规划）

时间：2021-07-30 21:03:38

　　copy：

　　Dilworth定理：DAG的最小链覆盖=最大点独立集

　　最小链覆盖指选出最少的链(可以重复)使得每个点都在至少一条链中

　　最大点独立集指最大的集合使集合中任意两点不可达

　　此题中独立的定义即是两点满足一个在左下一个在右上（或在同一格）。于是只需要找一条从左下到右上权值和最大的路径。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

int read()

{

    int x=,f=;char c=getchar();

    while (c<''||c>'') {if (c=='-') f=-;c=getchar();}

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

#define N 1010

int T,n,m,a[N][N],f[N][N];

int main()

{

#ifndef ONLINE_JUDGE

    freopen("bzoj3997.in","r",stdin);

    freopen("bzoj3997.out","w",stdout);

    const char LL[]="%I64d\n";

#else

    const char LL[]="%lld\n";

#endif

    T=read();

    while (T--)

    {

        n=read(),m=read();

        for (int i=;i<=n;i++)

            for (int j=;j<=m;j++)

            a[i][j]=read();

        for (int i=;i<=m;i++) f[n+][i]=;

        for (int i=n;i>=;i--)

            for (int j=;j<=m;j++)

            f[i][j]=max(a[i][j]+f[i+][j-],max(f[i+][j],f[i][j-]));

        cout<<f[][m]<<endl;

    }

    return ;

}

相关文章