「学习笔记
Background
最大子段和是最经典的 dp 问题了，但是最近书虫发现了最大子段和的另一个拓展算法 —— 拆块最大子段和。
拆块最大子段和可以用两步，书虫将其命名为：
- 拆开
- 组合
接下来我们将用一些例子来讲解这个算法。
Sample 0 P1115 最大子段和
Description
给定一个长度为 (n) 的序列 (a_i)，求出一段使得这一段的和最大。
(1 le n le 2 imes 10^5)，(|a_i| le 10^4)。
Solution
最大子段和板子，考虑 dp，定义 (dp[i]) 为 ([1,i]) 之间的最大子段和，那么对于第 (i) 个位置，可以考虑从 (dp[i-1]) 后面接 (a[i])，也可以选择单独开始一个子段，因此状态转移方程很容易就得出来了：
注：下文中 (maxlimits_{i in [l,r]}[a[i]]) 代表 (a[l]) 到 (a[r]) 的最大子段和。
Sample 1 P2545 [AHOI2004]实验基地
Step 1：Link。
Step 2：Link Step 1 的加强版，想投主题库没过（
Description
给定一个 (2 imes n) 的矩阵，第 (i) 行第 (j) 列的数为 (a_{i,j})。
求一个凹形块使得凹形块里的数字和最大。
凹形块定义为一个 (2 imes w_1) 的矩形，其中 (3 le w_1 le n)，然后在第一行把一块 (1 imes w_2) 的矩形挖掉，其中 (1 le w_2 le n-2)，要保证挖掉之后第一行左右都有残留的部分。
Step 1：(n le 3000)。
Step 2：(n le 5 imes 10^6)。
Solution for Step 1
凹形块就是类似下面这个图形：
---++---+++-
---++++++++-
我们尝试 拆开，也就是拆块最大子段和的第一步：
---++ --- +++-
---++ +++ +++-
如果我们不考虑第二步 组合，那么可以用一个 (mathcal O(n^2)) 的做法完成。
拆成的三部分中间的部分是枚举的部分，假设他为 ([l,r])，那么答案可以由三部分组成：
- 左边的是 (maxlimits_{i in [1,l-1]}[a[i][1]+a[i][2]])。
- 中间是 (displaystyle sumlimits_{i=l}^r a[i][2])。
- 右边的是 (maxlimits_{i in [r+1,n]}[a[i][1]+a[i][2]])。
因此，我们只需要枚举中间的区间 ([l,r]) 即可，时间复杂度 (mathcal O(n^2))。
这个算法可以轻松通过 Step 1。
Solution for Step 2
(mathcal O(n^2)) 会炸掉，我们需要 (mathcal O(n))。
我们发现上一个 Solution 仅仅是 拆开，没有 组合。
所以我们将这个凹形块重新拆开，省去左右的空白：
++ --- +++
++ +++ +++
拆开后，我们将其一一组合，发现有三种组合方式：
- 左，将其称为单独块，定义 (dp[i][1]) 为 (maxlimits_{k in [1,i]}[a[k][1]+a[k][2]])。
- 左 + 中，将其称为 L 形块，定义 (dp[i][2]) 为 ([1,i]) 中的最大 L 形块。
- 左 + 中 + 右，即为凹形块，定义 (dp[i][3]) 为 ([1,i]) 中的最大凹形块。
不难发现，这三块可以同时计算：
- 左的单独块就是普通的最大子段和。
- 左 + 中的 L 形块可以是从左的单独块接上一个 (a[i][2]) 或者左 + 中的 L 形块接上一个 (a[i][2])，即为：
- 左 + 中 + 右的凹形块可以是从左 + 中的 L 形块接上一个 (a[i][1]+a[i][2]) 或者左 + 中 + 右的凹形块接上一个 (a[i][1]+a[i][2])，即为：
我们就可以 (mathcal O(n)) 计算了，回顾本题，我们将其 拆开 为三块，然后 组合 计算，很容易就完成了拆块最大子段和。
是不是还挺简单的？
Practice 1 P7160 「dWoi R1」Sixth Monokuma's Son
这题将不会详细的讲述如何 拆开 和 组合，而是将直接讲述 拆开 和 组合 的结果。
Description
给定一个 (n imes m) 的矩阵，第 (i) 行第 (j) 列的数为 (a[i][j])。
求一个矩形环使得环里的数之和最大。
矩形环定义为一个 (n imes w_1) 的矩阵，其中 (3 le w_1 le m)，然后在中间选取一个 ((n-2) imes w_2) 的矩阵挖掉，第一行和最后一行要保留，其中 (1 le w_2 le (m-2))，且挖掉这个矩阵之后上下左右都要有保留的部分。
Step 1：(n le 10)，(m le 1000)。
Step 2：(n le 10)，(m le 10^5)。
Solution for Step 1
一个矩阵环即为：
---+++++--
---+--++--
---+--++--
---+++++--
拆开 结果如下所示：
---+ ++ ++--
---+ -- ++--
---+ -- ++--
---+ ++ ++--
我们还是枚举中间的 ([l,r])，然后左右算最大子段和。
(mathcal O(n^2))，期望得分 (50)。
Solution for Step 2
重新 拆开：
+ ++ ++
+ -- ++
+ -- ++
+ ++ ++
然后 组合 为三部分：
- 左的单独块。
- 左 + 中的 C 形块。
- 左 + 中 + 右的矩形环。
具体细节请读者自行完善，可以做到 (mathcal O(m))（输入省略）。