仓库源文，站点原文

title: "题解 - [Luogu P3974] [TJOI2015] 组合数学" categories:

原始题面

为了提高智商, ZJY 开始学习组合数学. 某一天她解决了这样一个问题: 给一个网格图, 其中某些格子有财宝. 每次从左上角出发, 只能往右或下走. 问至少要走几次才可能把财宝全捡完

但是她还不知足, 想到了这个问题的一个变形: 假设每个格子中有好多块财宝, 而每一次经过一个格子至多只能捡走一块财宝, 其他条件不变, 至少要走几次才可能把财宝全捡完?

这次她不会做了, 你能帮帮她吗?

第一行为一个正整数 $t$, 表示数据组数

每组数据的第一行是两个正整数 $n$ 和 $m$, 表示这个网格图有 $n$ 行 $m$ 列

接下来 $n$ 行, 每行 $m$ 个非负整数, 表示这个格子中的财宝数量 ($0$ 表示没有财宝)

对于每组数据, 输出一个整数, 表示至少走的次数

对于 $30\%$ 的数据, $n \le 5$, $m \le 5$, 每个格子中的财宝数不超过 $5$ 块

对于 $50\%$ 的数据, $n \le 100$, $m \le 100$, 每个格子中的财宝数不超过 $1000$ 块

对于 $100\%$ 的数据, $1\le t\le 2$, $1\le n \le 1000$, $1\le m \le 1000$, 每个格子中的财宝不超过 $10^6$ 块

利用拟阵, 我们可以在 DAG 的路径和偏序集的链, 以及 DAG 的点独立集与和偏序集的反链建立同构映射

所以 DAG 上的 Dilworth 定理变为:

<center><p>DAG 的最小链覆盖数等于最大的点独立集元素数</p></center>

故本题即为求给定网格图的最大点权独立集的点权和

令 $f(i,j)$ 为从 $(i,j)$ 到 $(1,m)$ 这个子网格中的最大点权独立集的点权和, 注意到每个点都和其右上角的点不相邻, 则状态转移方程为

$$ f(i,j)=\max{f(i-1,j),f(i,j+1),f(i-1,j+1)+a_{ij}} $$

答案即为 $f(n,1)$

<details open> <summary><font color='orange'>Show code</font></summary> {% icodeweb cpa_cpp title:Luogu_P3974 Luogu/P3974/0.cpp %} </details>