题目分析

本题要求从网格左上角 $(1,1)$ 出发，每次只能向右或向下移动，到达右下角 $(N,M)$。每个格子 $(i,j)$ 有 $a_{i,j}$ 块财宝，每次经过一个格子最多只能捡走一块财宝。问至少需要走多少次才能捡完所有财宝。

关键转化

这个问题可以转化为最小路径覆盖问题。根据 Dilworth 定理，在 DAG 中，最小路径覆盖数等于最大反链的大小。

在本题的网格图中：

定义偏序关系：点 $(i,j) \leq (i',j')$ 当且仅当 $i \leq i'$ 且 $j \leq j'$

反链是指集合中任意两点不可比较，即从左上到右下的任何路径最多经过反链中的一个点

因此问题转化为求最大反链，即找到最大的点集，使得从 $(1,1)$ 到 $(N,M)$ 的任何路径最多经过该集合中的一个点

算法思路

使用动态规划求解。定义 $dp[i][j]$ 表示从 $(i,j)$ 到 $(N,M)$ 这条路径上的最大反链大小。

状态转移方程： dp[i][j]=max(dp[i−1][j],dp[i][j+1])+a[i][j] 最终答案就是 $dp[N][1]$。

算法核心思想

1.空间优化：

使用一维数组 $flw[j]$ 代替二维 $dp$ 数组，$flw[j]$ 实际上存储的是 $dp[i][j]$ 的值

2.单调栈维护：

$stk$ 数组维护一个单调递增的栈（按 $flw$ 值）

当当前财宝数 $x$ 大于 $flw[j]$ 时，需要向前"借流量"

通过弹出栈顶元素并调整流量，保证单调性

3.最终答案计算：

$ans = \sum_{i=1}^{n} (IMX - flw[0])$，其中 $IMX - flw[0]$ 就是第 $i$ 行对最终最大反链的贡献

复杂度分析

时间复杂度：$O(T \times N \times M)$，每个格子最多入栈出栈一次

空间复杂度：$O(M)$，只需要一维数组和栈

总结

本题通过 Dilworth 定理将最小路径覆盖问题转化为最大反链问题，再使用单调栈优化的动态规划高效求解，在 $O(N \times M)$ 的时间和 $O(M)$ 的空间内解决了问题。