问题分析

我们有一个 $N \times N$ 的网格，每列可以建一个高度为 $k$ 的堤坝（覆盖第 $0$ 到 $k-1$ 行）。一条鱼 $(x, y)$ 能被抓住的条件是：

1. 自己列没被覆盖：$h_x \le y$
2. 相邻列有高堤坝：$h_{x-1} > y$ 或 $h_{x+1} > y$

目标：选择每列堤坝高度，最大化能抓住的鱼的重量和。

代码思路解析

这是一个动态规划 + 线段树优化的高效解法。

核心状态设计

代码使用了两个主要状态：

• f[z][0]：当前列堤坝高度为某个值时，由左边堤坝抓住的鱼的最大收益
• f[z][1]：当前列堤坝高度为某个值时，由右边堤坝抓住的鱼的最大收益

关键数据结构

struct SegT {
    ll sg[(N << 2) + 5];  // 线段树数组
    bool tg[(N << 2) + 5]; // 懒标记
    // 支持单点更新和区间查询
};

算法流程

1. 数据预处理

for (int i = 0; i < m; i++)
    v[Vx[i] + 1].pb({Vy[i] + 1, Tw[i]});

将鱼的坐标从0-based转为1-based，并按列分组。

2. 初始化第一列

sort(v[1].begin(), v[1].end());
ll t = 0;
for (pii i : v[1])
    t += i.se, f[0][0].chg(i.fi, 1, n, 1, t);

对第一列的鱼按行排序，累加重量并更新线段树。

3. 动态规划转移

对于每列 $i$（从2到n）：

• 清空状态：重置线段树为 -Inf

• 更新 f0：记录不建堤坝时的最大收益

• 处理 f[z][1]（由右边堤坝抓住）：

  for (pii j : v[i])
      f[z][1].chg(j.fi, 1, n, 1, 
          max(max(f[z][1].qmx(j.fi + 1, n, 1, n, 1), 
                f[z^1][1].qmx(j.fi + 1, n, 1, n, 1)), 
          f0[z^1]) + j.se);
  

  如果当前列堤坝高度 > 鱼的行，鱼可以被右边堤坝抓住

• 处理 f[z][0]（由左边堤坝抓住）：

  for (pii j : v[i])
      f[z][0].chg(j.fi, 1, n, 1,
          max(max(f[z^1][1].sg[1], f[z][0].qmx(1, j.fi - 1, 1, n, 1)),
             max(f[z^1][0].qmx(1, j.fi - 1, 1, n, 1), f0[z^1])) + j.se);
  

  如果当前列堤坝高度 ≤ 鱼的行，且前一列堤坝高度 > 鱼的行，鱼可以被左边堤坝抓住

4. 最终答案

return max(f[z^1][1].qmx(1, n, 1, n, 1), f0[z^1]);

算法正确性

这个解法能确保正确性的原因：

1. 状态完备性：f[z][0] 和 f[z][1] 覆盖了所有可能的捕捉情况
2. 无后效性：通过滚动数组，每列只依赖前一列的状态
3. 最优子结构：线段树维护了所有高度对应的最优解

复杂度分析

• 时间复杂度：$O(M \log N)$
  • 每列鱼处理一次，每次线段树操作 $O(\log N)$
• 空间复杂度：$O(N)$
  • 线段树大小 $O(N)$，鱼存储 $O(M)$

关键优化技巧

1. 线段树优化：将 DP 转移复杂度从 $O(N^2)$ 降为 $O(M \log N)$
2. 滚动数组：节省空间，只保存前后两列状态
3. 按行排序：方便计算重量累加和

示例验证

对于题目例子：

N=5, M=4
鱼: (0,2,5), (1,1,2), (3,3,3), (4,4,1)

算法会找到最优解：选择鱼 0 和 3，总重量 8。

算法标签

• 动态规划
• 线段树
• 区间查询
• 贪心思想

总结

这个解法巧妙地利用了线段树来优化 DP 转移，通过分离"由左堤坝抓住"和"由右堤坝抓住"两种状态，避免了传统二维 DP 的高复杂度。对于 $N \le 10^5$, $M \le 3\times 10^5$ 的大规模数据，能够在合理时间内求解，是本题的高效解法。