51Nod1051 最大子矩阵和

Problem

一个M*N的矩阵,找到此矩阵的一个子矩阵,并且这个子矩阵的元素的和是最大的,输出这个最大的值。

例如:3*3的矩阵:

-1 3 -1

2 -1 3

-3 1 2

和最大的子矩阵是:

3 -1

-1 3

1 2

Solution

枚举上下边界,竖着加起来,横向算最大字段和。

Code

#include<stdio.h>
#include<set>
//#include<iostream>
#include<algorithm>
typedef long long ll;
typedef long double ld;
typedef double db;
//#define io_opt ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
int m,n;
ll a[520][520];
ll f[520];
ll sum[520][520];
ll mx=0;
int main() {
    //io_opt;
    scanf("%d%d",&m,&n);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            scanf("%lld",&a[i][j]);
            sum[i][j]=sum[i-1][j]+a[i][j];
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=i;j<=n;j++){
            for(int k=1;k<=m;k++){
                f[k]=max(0LL,f[k-1]+sum[j][k]-sum[i-1][k]);
                mx=max(mx,f[k]);
            }
        }
    }
    printf("%lld\n",mx);
    return 0;
}
上一篇:520表白神器,让女友对你死心塌地


下一篇:双目摄像头LeMTC-520初试