解题：TJOI 2015 组合数学

通过这个题理解了一下反链的概念，更新在图论知识点里了

每个点向右和下连边可以建出一张图，这个题事实上是让我们求图的最小链覆盖。Dilworth定理告诉我们，最小链覆盖等于最长反链(反链：DAG中的一个点集，其中的点两两不可达)，所以我们在横/纵一个方向上反着做dp即可(另一个方向正着，这里以从下往上，从左往右为例)，每次从左，下和左下转移来。

只在从左下转移来有一个$a[i][j]$的贡献，为什么？

因为只有这时两个点互相不可达，符合反链的条件(可以看出这样的一对角线上的点都是满足这个条件的)。这也是为什么我们只在一个方向上反着做，因为两个方向都反着做那不叫求最长反链，那是建了一张反图，本质上和直接正着做是一样的=。=

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 const int N=;

 int mapp[N][N],dp[N][N];

 int T,n,m;

 int main ()

 {

     scanf("%d",&T);

     while(T--)

     {

         memset(dp,,sizeof dp);

         scanf("%d%d",&n,&m);

         for(int i=;i<=n;i++)

             for(int j=;j<=m;j++)

                 scanf("%d",&mapp[i][j]);

         for(int i=n;i;i--)

             for(int j=;j<=m;j++)

                 dp[i][j]=max(dp[i+][j-]+mapp[i][j],max(dp[i+][j],dp[i][j-]));

         printf("%d\n",dp[][m]);

     }

     return ;

 }

巴特西

解题：TJOI 2015 组合数学

最新文章

热门文章