---

D. Boss, Thirsty 详细题解

1. 问题重述与转化

我们有一个 $n \times m$ 的网格，第 $i$ 行第 $j$ 列的值为 $A_{i,j}$。

• 第 $i$ 天必须选择 至少一个连续段（子数组）$[l_i, r_i]$（$1 \le l_i \le r_i \le m$），当天利润为：$$\text{profit}_i = \sum_{j=l_i}^{r_i} A_{i,j}$$
• 相邻两天必须满足：
  • 至少有一个公共类型（$\{l_i, \dots, r_i\} \cap \{l_{i-1}, \dots, r_{i-1}\} \neq \emptyset$）
  • 至少有一个新类型（$\{l_i, \dots, r_i\} \not\subseteq \{l_{i-1}, \dots, r_{i-1}\}$）

目标：最大化 $\sum_{i=1}^n \text{profit}_i$。

---

2. 关键转化：用“边”代替“格子”

考虑一行 $m$ 个格子，有 $m+1$ 条边，编号 $0, 1, \dots, m$。
格子 $j$（$1 \le j \le m$）位于边 $j-1$ 与边 $j$ 之间。

选择格子区间 $[l, r]$（$l \le r$）等价于选择两条不同的边：

$$l' = l-1,\quad r' = r$$

使得区间包含边 $l'$ 到边 $r'$ 之间的所有格子。

为了简便，我们直接定义：

• 左端点 $L = l-1$（0-based 边编号，范围 $0 \dots m-1$）
• 右端点 $R = r$（范围 $1 \dots m$）

那么区间为 $(L, R]$ 表示格子 $L+1$ 到 $R$。

利润：

$$\text{profit} = \sum_{j=L+1}^{R} A_{i,j}$$

定义前缀和：

$$\text{pref}[0] = 0,\quad \text{pref}[k] = \sum_{j=1}^k A_{i,j} $$

那么利润为：

$$\text{profit} = \text{pref}[R] - \text{pref}[L]$$

其中 $0 \le L < R \le m$。

---

3. 相邻天的约束转化

第 $i-1$ 天选择了 $[L', R']$（$L' < R'$）。
第 $i$ 天选择 $[L, R]$（$L < R$）。

条件：

1. 至少一个公共格子
   区间 $[L+1, R]$ 与 $[L'+1, R']$ 有交集
   $\iff L+1 \le R'$ 且 $L'+1 \le R$
   这等价于 $L < R'$ 且 $L' < R$。

2. 至少一个新格子
   区间 $[L+1, R]$ 不是 $[L'+1, R']$ 的子集
   $\iff$ 要么 $L+1 < L'+1$（左端新），要么 $R > R'$（右端新）。

合并两个条件，可以证明等价于：

$$\text{至少满足以下一条：} \quad L < L' < R \quad \text{或} \quad L < R' < R $$

也就是说，新区间必须严格包含上一区间的至少一个端点（左端点 $L'$ 或右端点 $R'$）。

---

4. 动态规划状态设计

因为只需要知道上一个区间的端点之一，可以设计两种 DP：

• $dpL[i][L]$：处理完前 $i$ 行，且第 $i$ 行选择的区间左端点为 $L$ 的最大总利润。
• $dpR[i][R]$：处理完前 $i$ 行，且第 $i$ 行选择的区间右端点为 $R$ 的最大总利润。

其中 $L \in [0, m-1]$，$R \in [1, m]$。

---

5. 转移方程

假设我们已经知道第 $i-1$ 行的 $dpL$ 和 $dpR$，现在要计算第 $i$ 行的 $dpL, dpR$。

第 $i$ 行选择区间 $[L, R]$，利润：

$$\text{profit} = \text{pref}_i[R] - \text{pref}_i[L] $$

上一行区间的端点（左或右）记为 $p$，要求 $L < p < R$。

如果上一行是以 $p$ 作为左端点，则上一行利润为 $dpL[i-1][p]$；
如果是以 $p$ 作为右端点，则上一行利润为 $dpR[i-1][p]$。
我们取最大值：

$$bestPrev[p] = \max(dpL[i-1][p], dpR[i-1][p])$$

于是：

$$dpR[i][R] = \max_{0 \le L < p < R} \left[ -\text{pref}_i[L] + bestPrev[p] + \text{pref}_i[R] \right] $$$$dpL[i][L] = \max_{L < p < R \le m} \left[ -\text{pref}_i[L] + bestPrev[p] + \text{pref}_i[R] \right] $$

---

6. 高效计算（前缀/后缀最大值优化）

6.1 计算 $dpR[i][R]$

固定 $R$，我们要最大化：

$$-\text{pref}_i[L] + bestPrev[p]$$

其中 $L < p < R$。

这可以分两步：

1. 先对所有 $p$，计算：

   $$val[p] = bestPrev[p] + \max_{0 \le L < p} (-\text{pref}_i[L]) $$

   其中 $\max_{L<p} (-\text{pref}_i[L])$ 是前缀最大值（从 $L=0$ 到 $p-1$）。

2. 再对 $R$，取：

   $$dpR[i][R] = \text{pref}_i[R] + \max_{0 \le p < R} val[p] $$

   这里 $\max_{p<R} val[p]$ 也是前缀最大值。

所以可以在 $O(m)$ 内求出所有 $dpR[i][R]$。

6.2 计算 $dpL[i][L]$

对称地，固定 $L$：

$$dpL[i][L] = -\text{pref}_i[L] + \max_{L < p < R \le m} \left[ bestPrev[p] + \text{pref}_i[R] \right] $$

先对每个 $p$ 计算：

$$val2[p] = bestPrev[p] + \max_{R > p} \text{pref}_i[R] $$

其中 $\max_{R>p} \text{pref}_i[R]$ 是后缀最大值。

然后：

$$dpL[i][L] = -\text{pref}_i[L] + \max_{p > L} val2[p] $$

这也是后缀最大值。

---

7. 算法步骤总结

1. 对每一行 $i$ 预处理前缀和 $\text{pref}_i[0..m]$。
2. 初始化第一行：
   • 对所有 $0 \le L < R \le m$，$dpL[1][L] = dpR[1][R] = \text{pref}_1[R] - \text{pref}_1[L]$（直接取区间 $[L,R]$）。
   • 但第一行没有前一行约束，所以 $dpL[1][L]$ 应取所有 $R>L$ 的最大利润：$$dpL[1][L] = \max_{R>L} (\text{pref}_1[R] - \text{pref}_1[L]) $$同理 $dpR[1][R] = \max_{L<R} (\text{pref}_1[R] - \text{pref}_1[L])$。 这也可以前缀/后缀最大值 $O(m)$ 求。
3. 对 $i = 2$ 到 $n$：
   • 计算 $bestPrev[p] = \max(dpL[i-1][p], dpR[i-1][p])$。
   • 用前缀最大值求所有 $dpR[i][R]$。
   • 用后缀最大值求所有 $dpL[i][L]$。
4. 答案为 $\max(\max_L dpL[n][L], \max_R dpR[n][R])$。

---

8. 时间复杂度

• 每行 $O(m)$，共 $n$ 行 → $O(nm)$。
• 所有测试用例的 $\sum nm \le 2\times 10^5$，完全可行。

---