看到这道题感觉像是网络流,如果没有权值,可以用DAG最小路径覆盖,有权值,感觉可以求一个上下界最小可行流,但内存卡了....时间估计也悬.

正解要用到一些数学知识,这里梳理一下:

定义:

　　偏序关系: 满足自反,反对称,传递的关系是自反关系

　　链: 偏序集A的一个子集B,并且满足B中元素两两可比

　　反链: 偏序集A的一个子集B,并且满足B中元素两两不可比

　　集合的划分: 集合A的划分是很多个集合,这些集合的交集为空,并集为A

Dilworth定理:

　　偏序集的最长反链的大小等于最小链划分

另一个定理:

　　偏序集的最长链大小等于最小反链划分

第二个定理很好证明,网上有很多,第一个定理大概感受一下吧.

所以这道题其实就求一个偏序集的最小链划分,我们用第一个定理,就是求它的最长反链,这个可以用DP搞定.

 

总结一下:

　　1, 一个集合及其偏序关系与一个DAG相对应, 或者说偏序集的图论本质便是一个DAG.

　　2, 求一个偏序关系的最长反链:

　　　　1) 如果该偏序关系的否也是一个类偏序关系,那么直接求后者的最长链长度就行了(比如(a,b)R(c,d) <=> a<=c and b<=d 就是这样一种关系).

　　　　2) 如果该偏序关系没有这样的性质,就用第一个定理把原问题转换成求DAG的最少路径覆盖问题.

 

1 #include 
      
        2 #include 
       
         3 #define max(a,b) ((a)>(b)?(a):(b)) 4 #define N 1010 5  6 int n, m; 7 int aa[N][N]; 8 int dp[N][N], up[N][N], rg[N][N]; 9 10 int main() {11     int T;12     scanf( "%d", &T );13     while( T-- ) {14         scanf( "%d%d", &n, &m );15         for( int i=1; i<=n; i++ ) 16             for( int j=1; j<=m; j++ ) 17                 scanf( "%d", &aa[i][j] );18         memset( up, 0, sizeof(up) );19         memset( rg, 0, sizeof(rg) );20         for( int i=1; i<=n; i++ ) 21             for( int j=m; j>=1; j-- ) {22                 dp[i][j] = aa[i][j] + max( up[i-1][j+1], rg[i-1][j+1] );23                 up[i][j] = max( dp[i][j], up[i-1][j] );24                 rg[i][j] = max( dp[i][j], rg[i][j+1] );25             }26         int ans = 0;27         for( int i=1; i<=n; i++ )28             ans = max( ans, dp[i][1] );29         for( int j=1; j<=m; j++ )30             ans = max( ans, dp[n][j] );31         printf( "%d\n", ans );32     }33 }