首页 > itarticle > 「tjoi2015」组合数学

「tjoi2015」组合数学

admin 11月 13, 2020 0

Source

TJOI2015
bzoj5481

Hint

请先思考后再展开

转dag，求最小链覆盖

Solution

请先思考后再展开

根据Dilworth定理，最小链覆盖=最小反链
然后每个点按权值拆开来，他们一定在同一条反链上
然后他一定是形如一个递增序列的
那么dp(i,j)表示结尾在(i,j)右上角的最长反链
然后就可以直接dp了

int a[MAX_N][MAX_N];
ll f[MAX_N][MAX_N];
void ()
{
    int T=qread();
    while(T--)
    {
        int n=qread(),m=qread();memset(f,0,sizeof f);
        for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) a[i][j]=qread();
        for(int i=1;i<=n;i++) for(int j=m;j>=1;j--)
            f[i][j]=max( max(f[i-1][j],f[i][j+1]),f[i-1][j+1]+a[i][j] );
        write2(f[n][1]);
    }
}