牛客NOIP暑期七天营-普及组1-D矩阵

矩阵

https://ac.nowcoder.com/acm/contest/916/D

题目大意:给定一个n*m的矩阵,输出最大子矩阵(元素之和最大值)。

对于每一个子矩阵,如果左上角是(x, y),右下角是(p, q),那么他每一行的元素之和是:

用乘法分配率合并后即:

这样,问题就转化为求数组a中的最大子段和以及数组b中的最大子段和问题了。

当然,还需要注意细节:

1、对于正数:两边都取最大子段和

2、对于负数:两边都取最小子段和

3、一个全正,一个全负:正数取最小值、负数取最大值(绝对值尽量小、乘积绝对值尽量小)

当然,只要某个数列既有正值又有负值,就不会出现第三种情况。

不管怎样,全部求一遍答案就出来了。

最后,关于赋初值:前缀和初值可以是0,因为前0个是可以用的;最大区间和、最小区间和就不能为0,取第一个数做初值比较保险。

#include <bits/stdc++.h>
#define N 100005
using namespace std;
int n, m, i, j, k, l, a[N];
long long x, y, ax, ay, bx, by, s[N];
int main(){
    scanf("%d%d", &n, &m);
    ax = bx = -101, ay = by = 101;
    for(x=y=0, i=1; i<=n; i++){
        scanf("%d", &a[i]);
        s[i] = s[i-1] + a[i];
        ax = max(ax, s[i]-y);//最大区间和 
        ay = min(ay, s[i]-x);//最小区间和 
        x = max(x, s[i]);//前面最大前缀和 
        y = min(y, s[i]);//前面最小前缀和 
    }
    for(x=y=0, i=1; i<=m; i++){
        scanf("%d", &a[i]);
        s[i] = s[i-1] + a[i];
        bx = max(bx, s[i]-y);//最大区间和 
        by = min(by, s[i]-x);//最小区间和 
        x = max(x, s[i]);//前面最大前缀和 
        y = min(y, s[i]);//前面最小前缀和 
    }
    x = max(ax*bx, ay*by);
    y = max(ax*by, ay*bx);
    printf("%lld\n", max(x, y));
    return 0;
}
全部评论

相关推荐

本人什么都不会求求大家帮我选一个简单一点的
牛客798552099号:选10 目标检测真的很简单 网上随便找点改进的模块拼一下就可以了
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务