聪明的矿工

聪明的矿工

时间： 1ms        内存：128M

描述：

小陈不好好学习，毕业之后为了生计，不得去矿场挖矿（真惨），小陈实地考察了下矿场，发现矿场是一个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

提示：

参考答案（内存最优[1944]）：

#include<stdio.h>
int main()
{

        int n;
        int a[500][500];
        int i,j,k;
            int max=0,b=0;
                scanf("%d",&n);
        for(i=0;i<n;i++)
            for(j=0;j<n;j++)
        scanf("%d",&a[i][j]);
        for(i=0;i<n;i++)
        for(j=1;j<n;j++)
        a[i][j]=a[i][j-1]+a[i][j];
    for(k=0;k<n;k++)
    {
    for(j=k;j<n;j++)
        {
            b=0;
            for(i=0;i<n;i++)
    {
            if(b>0)
            {if(k==0)
            b+=a[i][j];
            else
                b+=a[i][j]-a[i][k];
            }
            else
                b=a[i][j];
            if(b>max)
                max=b;
    }
        }}
        printf("%d",max);
}

参考答案（时间最优[0]）：

#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;
}

题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。