题解：P3974 [TJOI2015] 组合数学

xiayuanxia · 2025-04-07 13:12:37 · 题解

P3974 [TJOI2015] 组合数学

Dilworth 定理告诉我们：最小链覆盖数 = 最大反链的大小。

在本题中： 链：一条路径（从左上到右下的合法移动序列）。 反链：一组格子，其中任意两个格子 (i,j) 和 (x,y) 满足 i \leq x 且 j \geq y（即一个在另一个的“左下方向”，无法被同一条路径覆盖）。

建模为偏序集：

把每个有财宝的格子 (i,j) 看作一个元素。

定义偏序关系：(i,j) \leq (x,y) 当且仅当 i \leq x 且 j \leq y（即可以从 (i,j) 向右或向下走到 (x,y)）。

反链：一组格子，其中任意两个格子不可比，即一个在另一个的“左下方向”。

最大反链：

• 我们需要找到最大的反链，即最多有多少个格子满足互相无法被同一条路径覆盖。
• 这些格子必须满足：对于任意两个 (i,j) 和 (x,y)，要么 i < x 且 j > y，要么 i > x 且 j < y（即不能同时满足 i \leq x 和 j \leq y）。

转化为网格上的“对角线”问题： 观察发现，反链的格子必须分布在不同的“反对角线”上（即 i + j 为常数的线）。 最大反链的大小 = 所有反对角线上财宝总数的最大值。

每次路径可以覆盖一个“链”（即一系列可比较的格子）。

最少路径数 = 最小链覆盖数 = 最大反链的大小。

最大反链的大小 = 网格中无法被同一条路径覆盖的格子财宝总数的最大值。

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1005;
int t, n, m;
int a[N][N], dp[N][N];

int main() {
    cin >> t;
    while (t--) {
        cin >> n >> m;
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
                cin >> a[i][j];

        // 动态规划计算最大反链和
        for (int i = 1; i <= n; i++)
            for (int j = m; j >= 1; j--)
                dp[i][j] = max(dp[i-1][j+1] + a[i][j], max(dp[i-1][j], dp[i][j+1]));

        cout << dp[n][1] << endl;
    }
    return 0;
}