自动搬运

查看原文

来自洛谷，原作者为

	WeLikeStudying 

搬运于2025-08-24 22:39:31，当前版本为作者最后更新于2022-08-14 20:44:11，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

• 珍惜这道近年来比较简单的 IOI 题！

题意

• 有一个 $n\times n$ 的网格，里面有 $m$ 条鲶鱼，都有各自的重量。
• 你可以建一些从 $(x,0)$ 到 $(x,y)$ 的堤，如果鲶鱼在 $(x,y)$ 处，那么它被捕获当且仅当 $(x-1,y)$ 或 $(x+1,y)$ 处有堤且 $(x,y)$ 处没堤。
• 求可捕获鲶鱼的最大总重量，$n\le 10^5,m\le 3\times 10^5$。

分析

• 考虑 $O(n^2)$ 的暴力怎么做，尝试按行 DP，你发现或这个条件比较丑陋，且只考虑一种情况（对于第 $i$ 行的贡献，只考虑第 $i-1$ 行的帮助或第 $i+1$ 行的帮助）并没有影响。
• 设 $f(i,j,0/1)$ 为第 $i$ 行建 $(i,0)$ 到 $(i,j)$ 的坝，前 $i-1/i$ 行能抓到的最大重量，则（设 $g(i,j)$ 为 $(i,0)$ 到 $(i,j)$ 的鲶鱼质量之和），拆掉 DP 式子里面无用的东西，则：

• 直接这样 DP 是 $O(n^3)$ 的，但是参变分离下，可以发现它是 $O(n^2)$ 的。
• 由于鲶鱼很少，本质不同的状态也很少，所以我们可以做到 $O(n+m)$，虽然没必要，代码。