歷屆試題 最大子陣 時(shí)間限制：1.0s 內(nèi)存限制：256.0MB 提交此題 問題描述 給定一個(gè)n*m的矩陣A，求A中的一個(gè)非空子矩陣，使這個(gè)子矩陣中的元素和最大。
其中，A的子矩陣指在A中行和列均連續(xù)的一塊。 輸入格式 輸入的第一行包含兩個(gè)整數(shù)n, m，分別表示矩陣A的行數(shù)和列數(shù)。 接下來n行，每行m個(gè)整數(shù)，表示矩陣A。 輸出格式 輸出一行，包含一個(gè)整數(shù)，表示A中最大的子矩陣中的元素和。 樣例輸入 3 3 -1 -4 3 3 4 -1 -5 -2 8 樣例輸出 10 樣例說明 取最后一列，和為10。 數(shù)據(jù)規(guī)模和約定 對(duì)于50%的數(shù)據(jù)，1<=n, m<=50； 對(duì)于100%的數(shù)據(jù)，1<=n, m<=500，A中每個(gè)元素的絕對(duì)值不超過5000。
最大子矩陣的做法是將矩陣變化， 就是把最大子矩陣變成最大連續(xù)子序列和，把二維變成一維。 如下圖 獎(jiǎng)每豎行的和記錄，形成一個(gè)新的矩陣， 這樣只需要枚舉所有的i，j，求i到j(luò)的連續(xù)和最大的數(shù)。 最后找到的就是一個(gè)矩陣
3 3-1 -4 33 4 -1-5 -2 8-1 -4 32 0 2-3 -2 10#include <iostream>#include <string>#include <cstring>#include <stdio.h>#include <cmath>using namespace std;long long d[600][600],p[600][600];int main(){ int n,m; while(cin>>n>>m) { int i,j; for(i=1;i<=n;i++) { for(j=1;j<=m;j++) { cin>>d[i][j]; } }//cout<<endl; for(j=1;j<=m;j++) { long long x=0; for(i=1;i<=n;i++) { x+=d[i][j]; p[i][j]=x; } } /* for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { cout<<p[i][j]<<' '; } cout<<endl; } */ int maxsum=-10000000; int x,y,z; for(i=1;i<=n;i++) { for(j=i;j<=n;j++) { int thissum=0; for(int k=1;k<=m;k++) { thissum+=p[j][k]-p[i-1][k]; if(thissum>maxsum) { x=i;y=j;z=k; maxsum=thissum; } if(thissum<0) thissum=0; } } } // cout<<x<< ' '<<y<<' '<<z<<endl; cout<<maxsum<<endl; }}新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
