河北大学程序设计训练营

奥马尔喜欢吃很多糖果，但不幸的是，大部分的糖果都不健康。所以他的父母找到了一种方法，给每个糖果打分，分数越高，糖果就越健康(分数是一个整数，可以是正的、零的或负的)。一个孩子和他的父母买了一些糖果，他们到了卖糖果的地方，所有的糖果都被存储在一个N*M的二维网格中，每一行有M个糖果。行从上到下从1到N编号，列从左到右从1到M编号，每个单元格包含一个糖果健康值。奇怪的是，这个二维网格中的糖果的健康值总是从上到下、从左到右依次增大，如下图

题目示例图

奥马尔想买完一个子矩阵中的所有糖果，请你编程序求出他所能买得的最大的糖果健康值。

输入格式:

输入的第一行是单个整数T，测试用例的数量(1≤T≤100)。每个测试用例开始一行包含空格隔开两个整数N M (1≤N,M≤1000)代表糖果网格的尺寸，紧随其后的是N行，每一个包含M个空格隔开整数，代表这一行糖果的健康值。网格中的每个整数将不小于- 2000，也不大于2000。

输出格式:

对于每个测试用例，打印包含单个整数的一行，该整数表示从非空子矩形中可以获得的健康值的最大总和。

输入样例:

在这里给出一组输入。例如：

1
3 3
-4 -2 -1
-3 2 3
1 4 5

输出样例:

在这里给出相应的输出。例如：

14

解题思想:

  • 子矩阵建立时一角固定(最大值得点)

  • 求子矩阵健康值和公式：

    f[i][j] = f[i][j - 1] + f[i - 1][j] - f[i - 1][j - 1] + w[i][j];

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <bits/stdc++.h>
using namespace std;

const int N = 1010;

int w[N][N],f[N][N];
int main()
{
    int T;
    cin >> T;
    while(T -- )
    {
        int ans = -1e9;
        memset(f, 0, sizeof(f));
        memset(w, 0, sizeof(w));
		
        int n,m; scanf("%d%d",&n,&m);
        for(int i = n; i; --i)
           for(int j = m; j; --j)
                scanf("%d", &w[i][j]);

        for(int i = 1; i <= n; ++i)
           for(int j = 1; j <= m; ++j)
           {   
               f[i][j] = f[i][j - 1] + f[i - 1][j] - f[i - 1][j - 1] + w[i][j];
               ans = max(ans, f[i][j]);
           }
        cout << ans << "\n";
    }
  
}