传送门:https://www.lydsy.com/JudgeOnline/problem.php?id=3997
Sol
根据dilworth定理
偏序集的最小链划分=最长反链
对于这题来说,把图建出来
可以发现图是一个DAG 题目等价于求最小路径覆盖
如果直接用网络流求的话T飞……
发现是个偏序问题,所以DAG上的最小路径覆盖=最长反链
即现在要找的东西就是一个集合S 所有的i,j不可达 求最大权值和
简单dp一下
#include <bits/stdc++.h> using namespace std; int T; long long dp[1005][1005]; int a[1005][1005]; int N,M; int main(){ scanf("%d",&T); while (T--){ scanf("%d%d",&N,&M); for (int i=1;i<=N;i++) for (int j=1;j<=M;j++) scanf("%d",&a[i][j]); memset(dp,0,sizeof(dp)); for (int i=1;i<=N;i++) for (int j=M;j>=1;j--) dp[i][j]=max(dp[i][j+1],max(dp[i-1][j+1]+a[i][j],dp[i-1][j])); printf("%lld\n",dp[N][1]); } return 0; }