子矩阵前缀和求助,玄关
  • 板块灌水区
  • 楼主Aakw_Tea
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/7/16 18:41
  • 上次更新2024/7/16 19:50:52
查看原帖
子矩阵前缀和求助,玄关
1211960
Aakw_Tea楼主2024/7/16 18:41

5分代码大抵是有very very big大问题:

#include<bits/stdc++.h>
using namespace std;
int n,m,a,sumj[1001][1001],sumo[1001][1001],maxn=-1e9,lja,ljb,p,q;
int main(){
    cin>>n>>m>>p>>q;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>a;
            //分别算他的奇数列和偶数列前缀和 
            sumo[i][j]=sumo[i-1][j]+sumo[i][j-1]-sumo[i-1][j-1];
            sumj[i][j]=sumj[i-1][j]+sumj[i][j-1]-sumj[i-1][j-1];
			if(j%2==0)
				sumo[i][j]+=a;
			else
				sumj[i][j]+=a;
        }
    }
    for(int i=1;i+p-1<=n;i++){
        for(int j=1;j+q-1<=m;j++){
        	lja=0;
			ljb=0; 
			//正常前缀和求区间和 
         	lja=sumo[i+p-1][j+q-1]-sumo[i+p-1][j-1]-sumo[i-1][j+q-1]+sumo[i-1][j-1];
            ljb=sumj[i+p-1][j+q-1]-sumj[i+p-1][j-1]-sumj[i-1][j+q-1]+sumj[i-1][j-1];
            //计算差值 
            int s=max(lja-ljb,ljb-lja);
            //比大小 
            maxn=max(maxn,s);
        }
    }
    cout<<maxn;
    return 0;
     
}

样例输入

3 4 2 3 1 5 2 3 2 3 4 2 8 2 4 3

样例输出

13

提示

【样例解释】 当选择如下子矩阵时,S 的值为 13,满足最大。 2 3 4 8 2 4

【数据范围约定】 对于 30%的数据保证 1≤n≤50,1≤m≤50。

对于 70%的数据保证 1≤n≤300,1≤m≤300。

对于 100%的数据保证 1≤n≤1000,1≤m≤1000。

另外,所有的数据保证 1≤p≤n,1≤q≤m, 1≤Wij≤100。

玄关

2024/7/16 18:41
加载中...