AT_agc033_d Complexity 题解

好题。

首先考虑最简单的区间 DP， 表示在横坐标 ，纵坐标 的最小复杂度，每次转移的时候枚举一下切割线，每次取 即可做到 的复杂度。

你会发现这个复杂度显然不太能接受。

我们考虑优化。不妨分析一下这个复杂度有什么性质。

直觉上来说，肯定是越大的矩形复杂度就越大。形式化的说，如果一个矩形的复杂度为 ，那么在这个矩形的基础上任意增加一行或者一列，新的矩形的复杂度至少是 。

证明比较无脑，直接数学归纳法即可。

INFO 证明
首先对于 的情况，我们直接枚举所有的情况，发现命题是成立的。

接下来我们考虑 的情况，归纳假设是上面的命题对于任意 ，大小是 的矩形都成立。显然这个时候只能竖着切。考虑此时的最优解左侧是 ，右侧是 ，那么去掉最右侧的格子就变成了左侧 右侧 ，应用归纳假设，右侧矩形的权值变小了，此时大矩形的权值 显然不会变得更劣。

接下来是 的情况，我们继续归纳，归纳假设是对于所有 小于 ，上面的命题对于 大小的矩形成立。

此时我们对第二个维度再应用归纳法。对于 ，证明和 是对称的，这里不再赘述。

考虑 的情况。此时我们已经有了两个假设：

• 对于所有 ，上面的命题对于 大小的矩形成立。
• 对于所有 ，上面的命题对于 大小的矩形成立。

我们分类讨论。在下方增加和在右侧增加是完全对称的，我们以在下方增加为例。

对于在下方增加一行的情况，考虑新矩形的最优分割。

• 横着切。此时有两种情况。
  • 分割出来的其中一个小矩形就是原来的矩形本身。考察我们计算代价的函数 ，这个权值肯定是大于 的。
  • 否则，假设变成了一个大小为 和 的两个矩形。去掉最后一行，变成 和 的矩形。应用归纳假设，其中一个的权值变小不会更劣。
• 竖着切。此时去掉这一行两个矩形的高都变小了。应用归纳假设。两个权值都变小最终的 也不会更劣。

然后我们就证明了这个东西。

那么，我们接下来就有一个简单的做法可以将复杂度优化到四次方。

考虑固定 ，不断向右侧扩展 ，此时矩形的代价会单调递增。此时的答案就是 。考虑 ，根据我们的引理， 单调递增， 单调递减。那么最优决策点就在两个函数交点之处。

考察 向右侧移动一步，此时 不变， 的每个位置与原来的每个位置相比都会增加一个非负整数，并且仍然保持其单调性。

可以证明，最优决策点一定会向右侧移动。在决策值相同的情况，选择最右侧的点。

INFO 证明
首先如果最优决策点仍然有 ，那么显然决策点不会左移（因为当前决策点是符合条件的更右侧的点）。

如果 （请注意 增加了一个值，并且在增加前两个函数相等，因此这里只有可能更大），那么 之前的值只可能更大（因为单调性），交点只有可能更靠右侧。

另外一个证明方法是反证法。

INFO 证明
不妨假设最优决策点向左移动了。假设新的决策点为 ，旧决策点为 。原本的函数是 ，向右移动之后是 。

考虑 这种情况，它是不可能发生的。因为这意味着在 处 ，但是在 处没这个性质。由于函数 单调递减，因此 。由于 处不是交点，因此 。但是在上个时刻有 。因而 ，这里我们推出来了 ，和我们增加一个数的假设矛盾。

那么，剩下的就是 的情况。考察 到 ，如果没变化，那么在上一个时刻也有 ，但是 违反了单调性假设。

而如果增大了，也就是 ，那么 ，，那么两者的 也会小于 ，答案变小，这应该是更优的决策点，从而推导出了矛盾。

因而，我们可以做一个双指针，同时维护右端点和最优决策点，每次右移时，我们同时尝试向右侧移动最优决策点。

需要注意这里的后效性比较难处理。这个时候可以按照面积从小到大转移，每次转移完成之后在新的面积处添加一个转移当前矩形的任务。

这样的复杂度是 。看上去很糟糕，但是实际上总状态数是 ， 都取到 的时候这个数是 ，，并且时间限制是 秒，比较可以接受。

但是实际写一下就会发现这个东西会 TLE（我写的第一个点跑了 秒，但是可能是 std::vector 常数太大了，并且我们稍后也有更加优秀的做法）。

对于这个做法对空间的处理，不难发现你如果每次对半砍，面积会减半，因此你最多切 次就会切成 的格子。实际算一下你会发现答案不会超过 。

因此我们可以使用一个经典的技巧，交换状态和答案。

令 表示满足纵坐标 ，横坐标 ，复杂度不超过 的最大的 。

此时的状态个数就是可以接受的了。

我们有两种转移。对于竖着切的情况，相当于在复杂度小于 的情况下连续向右侧跳两次。也就是 。由于我们刚才推出来的单调性，这个转移显然正确（因为越往右侧到达指定的 的代价就越小，第一次肯定尽可能往远处跳）。

第二种转移是横着切。

此时我们也有性质， 对于任意 都成立。这一点也好证明，因为你从小矩形一步一步加行和列，其复杂度单调递增，如果有一个小矩形在 下到不了，那么包含它的大矩形在 下也到不了。

和我们一开始优化到四次方的做法一样，考虑固定 ，将 向右侧移动。

令 ，那么转移是 ，即两者能到达的最远位置中最近的一个，在所有可能的转移中取最大值。

此时 单调递减， 单调递增。每次向右侧扩展， 的每个位置都要减少一个值，因此最优决策点仍然单调递增。证明和我们刚刚的证明是完全对称的。

双指针转移即可。复杂度 。

参考代码在这里。包含了四次方做法和 的做法。