首页 > 代码库 > hdu1081（最大子矩阵）

hdu1081（最大子矩阵）

2024-08-04 03:54:21   221人阅读

 

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1081

 

    分析：a[i][j]代表第i行，前j个数据的和；那么由a[i][j]可得sum[k][long]=a[k][j]-a[k][i-1];long=j-i+1;

sum[k][long]表示第k行，从第i个数开始到第j个数长度为long的和；又因为循环是连续的，所以long固定时，

一个子矩阵和就是sum[k][long];则最大子矩阵ans=max（Sum（sum[k][long]）,ans）；

 

 

#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>#include <queue>#include <cstdlib>#include <vector>#include <set>#include <map>#define LL long long#define inf 1<<30using namespace std;int a[110][110];int main(){    int n,temp;    while(scanf("%d",&n)>0)    {        memset(a,0,sizeof(a));        for(int i=1;i<=n;i++)        {            for(int j=1;j<=n;j++)                scanf("%d",&temp),a[i][j]=a[i][j-1]+temp;        }        int ans=-inf,sum=0;        for(int i=1;i<=n;i++)        {            for(int j=i;sum=0||j<=n;j++)            {                for(int k=1;k<=n;k++)                {                    if(sum<0)sum=0;                    sum+=a[k][j]-a[k][i-1];                    ans=max(ans,sum);                }            }        }        printf("%d\n",ans);    }}
View Code

 

hdu1081（最大子矩阵）


联系
我们