FoxAndFlowerShopDivOne

作者：王子健 徐明宽

关键词：枚举，动态规划，RMQ

题目简述

给定一块$N*M$的田地，每块田地上只可能是百合花$(L)$、牵牛花$(P)$、空地$(.)$这三种可能之一。

你的任务是找到两块非空的且无交集（不同时覆盖同一块土地）的矩形区域，满足这两块区域内百合花的数量与牵牛花的数量之差的绝对值不超过$K$，且使得区域内花的数量之和最大。

$2≤N,M≤30,0≤K≤900$

分析

我们把"$L$"看成$1$，"$P$"看成$-1$，"$.$"看成$0$，那么问题便等价为选出两块矩形区域满足区域内元素和在$[-K,K]$之间且使得区域内包含的非$0$元素尽量多。

其次我们可以发现，两块矩形的排列方式无外乎两种情况：

$1、$存在一条竖线将两块矩形区域隔开且不穿过两块矩形区域内部。

$2、$存在一条横线将两块矩形区域隔开且不穿过两块矩形区域内部。

由于两种情况是等价的，我们不妨只考虑第一种情况。

算法一

考虑使用动态规划算法来解决这道问题，设$f[i][k]$表示前$i$列选出一个元素和为$k$的矩形最多包含的非$0$元素的数量，设$g[i][k]$表示后$i$列选出一个元素和为$k$的矩形最多包含的非$0$元素的数量。

$f[i][k]$的求法：从小到大枚举$i$，那么最优矩形既可能是$f[i-1][k]$所表示的矩形，也可能是右边界为$i$的矩形。由于$N$的范围很小，我们不妨枚举所有第二种矩形来计算即可。$g[i][k]$的求法同理。

得到$f$和$g$数组后，我们枚举所有符合题意的分割线$x=i$、左边矩形的元素和$k1$与右边矩形的元素和$k2$，用$f[i][k1]+g[i+1][k2]$更新答案即可。

时间复杂度为$O((N+M)*K^2+N^2M^2)$。

算法二

同样使用动态规划算法计算出$f[i][k]$（前$i$列选出一个元素和为$k$的矩形最多包含的非$0$元素的数量），然后可以枚举右边的矩形（不妨设右边矩形的最左边一列为$i+1$）得到元素和$k2$，则可更新答案的$f[i][k1]$满足$k1 \in [-K - k2, K - k2]$，这是一个RMQ（询问区间最大值）问题，可以用$O((N+M)K\log K)$的时间预处理后每次$O(1)$询问。因为$K \leq NM$，所以总时间复杂度为$O(N^2M^2)$。