内存:128  时间:1

题目描述

小陈不好好学习,毕业之后为了生计,不得去矿场挖矿(真惨),小陈实地考察了下矿场,发现矿场是一个N*N大小的方形矿场(1<=N<=500),并且每个矿石都有一个价值,但是矿场内部也会有硫酸会腐蚀矿石,假设矿石价值为10,硫酸腐蚀是7,那么这两个一结合,矿石价值就只剩3.矿场有规定,必须是选择一个矩形大小的矿地挖掘,而且必须全挖掘完毕(不能只要矿石,而不要硫酸),假设小陈可以挖掘任意矩形大小的矿地,请问小陈从这片矿地最大可以获得多少利润,当然小陈不能做亏本的买卖哈。

输入

先输入N,表示矿场的大小,之后输入N行N列的数字,代表矿场中每一个部分的价值,正数代表矿石的价值,负数代表硫酸腐蚀矿石的能力。矿石价值大小是[0,10]之间,硫酸腐蚀能力大小是[-10,0]之间。

输出

小陈可以获得的最大利润X。

样例输入

4
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2

样例输出

15

提示

最大的矿地是
9 2 
-4 1 
-1 8 
利润是15

代码如下

#include <iostream>
#include <cstring>
using namespace std;

int a[502][502];
int colsum[502][502];

int main()
{
    int N;
    int max_num = 0;
    cin >> N;
    for( int i = 1; i <= N ; i++)
        for(int j = 1 ; j <= N ; j++){
            cin >> a[i][j];
            colsum[i][j] = colsum[i-1][j] + a[i][j];
        }
    for(int i = 0 ; i <= N ; i++)
    for(int  j = i ; j <= N ; j++){
        int sum = 0;
        for(int k = 1 ; k <= N ; k++){
            sum += colsum[j][k] - colsum[i][k];
            if(sum < 0)
                sum = 0 ;
            else
                max_num = max(sum, max_num);
        }
    }

    cout << max_num << endl;
    return 0;
}

代码来源于互联网,仅供参考!