题目描述

有一个被分成n*m格的巧克力盒，在(i,j)的位置上有a[i,j]块巧克力。就在送出它的前一天晚上，有老鼠夜袭巧克力盒，某些位置上被洗劫并且穿了洞。所以，你——王7的弟弟王9，必须从这个满目苍夷的盒子中切割出一个矩形巧克力盒，其中不能有被老鼠洗劫过的格子且使这个盒子里的巧克力尽量多。

输入格式：

第一行有两个整数 n、m。第 i+1行的第 j 个数表示a[ i , j ]。如果这个数为 0 ，则表示这个位置的格子被洗劫过。

输出格式：

输出最大巧克力数。

3 4
1 2 3 4
5 0 6 3
10 3 4 0

17
//10 3 4这个矩形的巧克力数最大

说明

1≤n,m≤300
0≤a[i,j]≤255

题解：

最大子矩阵和，枚举子矩阵的上边界和下边界

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int inf = 23333333;
int map[305][305];
int sum[305][305];
int main()
{
    int n, m, ans = 0;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            scanf("%d", &map[i][j]);
            if (!map[i][j])
                map[i][j] = -inf;
            sum[i][j] += sum[i-1][j] + map[i][j];
        }
    int ls = 0;
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j <= n; j++)
        {
            for (int k = 1; k <= m; k++)
            {
                ls += sum[j][k] - sum[i][k];
                if (ls < 0)
                    ls = 0;
                ans = max (ans, ls);
            }
            ls = 0;
        }
    cout << ans;
    return 0;
}