牛宫

柿子饼同学

题目如下 ，就是题解中的 minpre 数组的意思不理解，题解在下：

1. #include <bits/stdc++.h>
   
2. #define For(i, a, b) for (int i = (a); i <= (b); i++)
   
3. #define M 405
   
4. using namespace std;
   
5. int sum[M][M];
   
6. int s[M], minpre[M];
   
7. int main() {
   
8.     int n, m, x;
   
9.     scanf("%d%d", &n, &m);
   
10.     For(i, 1, n) {
    
11.         For(j, 1, m) {
    
12.             scanf("%d", &x);
    
13.             sum[i][j] = sum[i - 1][j] + x;  //维护列的前缀和
    
14.         }
    
15.     }
    
16.     int ans = 0;
    
17.     For(i, 1, n) {
    
18.         For(j, i, n) { // 这里是枚举矩阵的上下界
    
19.             int t = 0;
    
20.             s[0] = 0;
    
21.             For(k, 1, m) {
    
22.                 s[k] = s[k - 1] + sum[j][k] - sum[i - 1][k];  //维护行的前缀和
    
23.                 minpre[k] = min(minpre[k - 1], s[k]); // 这一句不知道什么意思
    
24.             }
    
25.             int len = 0;
    
26.             For(k, 1, m) {
    
27.                 while (len < k && s[k] > minpre[k - len - 1]) len++; // 还有这个，k 枚举的是右界，k-len-1 就是左界
    
28.             }
    
29.             ans = max(ans, (j - i + 1) * len); // 更新矩阵最大面积
    
30.         }
    
31.     }
    
32.     printf("%d", ans);
    
33.     return 0;
    
34. }

复制代码

输入输出 ：

1. 3 2
   
2. 4 0
   
3. -10 8
   
4. -2 -2

复制代码

1. 4

复制代码

柿子饼同学

懂了 , minpre 是前缀和中最小的那个