最小链覆盖=最长反链长度

所以题目等价于寻找一条从右上角到左下角的最长路

 

#include
     
      #include
      
       #include
       
        using namespace std;#define N 1002int a[N][N];long long dp[N][N];void read(int &x){    x=0; char c=getchar();    while(!isdigit(c)) c=getchar();    while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); }}int main(){    int T,n,m,x;    read(T);    while(T--)    {        read(n); read(m);        for(int i=1;i<=n;++i)            for(int j=1;j<=m;++j)                read(a[i][j]);        memset(dp,0,sizeof(dp));        for(int i=1;i<=n;++i)            for(int j=m;j;--j)                dp[i][j]=max(dp[i-1][j+1]+a[i][j],max(dp[i-1][j],dp[i][j+1]));        cout<
        
         <<'\n';    }}