hihoCoder 1502-最大子矩阵

---

给定一个N*M的矩阵，要从中找出一个元素最多的子矩阵，使得该子矩阵的和不超过K。 如果确定了子矩阵的左上角点和右下角点，则唯一确定了该子矩阵。所以我们可以用一种完全暴力的方法来试一下这个题。两层循环确定左上角点(i,j)，两层循环确定右下角点(u,v)，再两层循环累加从(i,j)到(u,v)的元素和，如果和不超过K，则更新最大元素个数，否则继续循环。复杂度为$$O(n^6)$$，TLE，但是能过40%的数据。 类似这样求子矩阵的和，子数组的和等问题，一般都需要求从0到i的累加和。网上有一题也是求最大子矩阵的问题，但是那道题定义子矩阵的大小是用子矩阵的和来定义的，而本题是用子矩阵中元素个数来定义的。但是原理差不多，可以参考。 定义一个二维数组sum[i][j]表示固定子矩阵的左上角坐标为(1,1)（假设矩阵的下标从1开始），当右下角坐标为(i,j)时，这个子矩阵的和是多少。则有： sum[i][j]=sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1]+matrix[i][j] 这个很好理解，相当于求面积，sum[i][j-1]+sum[i-1][j]加了两遍sum[i-1][j-1]，所以要减掉一个，最后再加上sum[i][j]独有的matrix[i][j]。 有了sum[i][j]之后，怎样求任意一个子矩阵的和呢？假设我们要求第i,j两行、u,v两列交成的子矩阵的和，应该怎样计算呢。这个也很好算，也是面积的加加减减，如下图所示，把(j,v)的面积减去(j,u)左边以及(i,v)上边的面积，但是(i,u)左上的面积减了两次，所以还要加上。总结成公式就是： cursum=sum[j][v]-sum[j][u-1]-sum[i-1][v]+sum[i-1][u-1]

      |               |
-----(i,u)----------(i,v)----
      |               |
      |               |
-----(j,u)----------(j,v)----
      |               |

通过cursum公式，我们很容易就能求出任意一个子矩阵的和了。但是要求和不超过K，且元素个数最多的子矩阵，还是免不了枚举起点和终点。所以最后求解的时候，我还是枚举了起点(i,j)和终点(u,v)，然后通过上述公式求到子矩阵的和cursum，如果cursum不超过K，则更新最大子矩阵元素个数。 但是，这种方法还是TLE了！在我几近绝望的时候，我试着把v的遍历顺序由u→m改成了由m→u。什么意思呢，因为要求元素个数最多，如果从u列到最大的m列的子矩阵和都不超过K，则此时的元素个数肯定是在这个循环里最大的，所以直接跳过了v从u→m-1的那些列。但是如果v的遍历顺序是u→m，则开始的好多v的子矩阵和都不超过K，这样的话，v就需要遍历很久才能找到一个超过K的子矩阵和，最坏的情况是，遍历到最大值m时的子矩阵和也不超过K，所以还不如从最大值往小的遍历。这么简单的一改，居然AC了！不知道会不会是数据太弱了，毕竟复杂度都是一样的$$O(n^4)$$。 代码如下： [cpp] #include<iostream> #include<cstdio> #include<vector> #include<algorithm> #include<unordered_map> #include<string> #include<climits> using namespace std; int main() { //freopen("input.txt", "r", stdin); int n, m, k; scanf("%d %d %d", &n, &m, &k); vector<vector<int>> matrix(n + 1, vector<int>(m + 1, 0)); int minvalue = INT_MAX; for (int i = 1; i <= n; ++i) { for (int j = 1; j <= n; ++j) { scanf("%d", &matrix[i][j]); minvalue = min(minvalue, matrix[i][j]); } } if (minvalue > k)printf("-1\n"); else if (minvalue == k)printf("1\n"); else { int ans = INT_MIN; vector<vector<int>> sum(n + 1, vector<int>(m + 1, 0)); for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { sum[i][j] = sum[i – 1][j] + sum[i][j – 1] – sum[i – 1][j – 1] + matrix[i][j]; } } for (int i = 1; i <= n; ++i) { for (int j = i; j <= n; ++j) { //for (int u = 1; u <= m; ++u) { // for (int v = u; v <= m; ++v) { // TLE // int cursum = sum[j][v] – sum[j][u – 1] – sum[i – 1][v] + sum[i – 1][u – 1]; // if (cursum <= k)ans = max(ans, (j – i + 1)*(v – u + 1)); // else break; // } //} for (int u = 1; u <= m; ++u) { for (int v = m; v >= u; –v) { int cursum = sum[j][v] – sum[j][u – 1] – sum[i – 1][v] + sum[i – 1][u – 1]; if (cursum <= k) { ans = max(ans, (j – i + 1)*(v – u + 1)); break; } } } } } printf("%d\n", ans); } return 0; } [/cpp] 本代码提交AC，用时169MS。]]>