Wannafly挑战赛19

矩阵

矩阵 M 包含 R 行 C 列，第 i 行第 j 列的值为 M(i,j)。
请寻找一个子矩阵，使得这个子矩阵的和最大，且满足以下三个条件：
子矩阵的行数不能超过 X 行。
子矩阵的列数不能超过 Y 列。
子矩阵中 0 的个数不能超过 Z 个。
请输出满足以上条件的最大子矩阵和。
去掉所有的条件后，可以发现是一个淳朴的二维矩阵求最大子矩阵。可以通过一维最大连续子数组的方式去解决它。
现在首先考虑第二个限制，就是限制了一维数组的个数。
现在，问题就转化为一维数组中，寻找连续的一段，保证0的出现次数的约束和数组长度的约束。
0出现的次数的前缀和与数组的长度都是单调递增的。所以可以通过单调队列的方式解决。
可以推广一下，如果在此时的一维数组中，需要约束的条件是单调的，也就是说，如果对于此位来说（队首元素不满足条件，需要出队），那么对于后面的位，后面的元素，也是不满足条件的。这样，就能满足单调性。