Luogu

LOJ

分析

假设现在有两个格子 $(x_1,y_1)$ 和 $(x_2,y_2)$,我们定义一个偏序关系 $\leq$ 为 $x_1\leq x_2$ 且 $y_1\leq y_2$。

那么我们就相当于要求给出的偏序集能划分成的最少的全序集的个数,根据 Dilworth 定理它等于最长反链的元素个数。

然后反链上的元素满足 $x_1\leq x_2\land y_1>y_2$,或者 $y_1\leq y_2\land x_1>x_2$。因此我们只需要从左上往右下 DP 就可以求出最长反链了。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#define re register
using namespace std;
typedef long long ll;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=1000+10;

int n,m,a[N][N]; ll dp[N][N];

int main() {
    int T=read();
    while (T--) {
        n=read(),m=read();
        for (re int i=1;i<=n;++i)
            for (re int j=1;j<=m;++j)
                a[i][j]=read();
        for (re int i=1;i<=n;++i)
            for (re int j=m;j;--j)
                dp[i][j]=max({dp[i-1][j],dp[i][j+1],dp[i-1][j+1]+a[i][j]});
        printf("%lld\n",dp[n][1]);
    }
    return 0;
}
最后修改:2020 年 01 月 12 日 08 : 41 PM