首页 > 代码库 > hdu 1081(最大子矩阵和)
hdu 1081(最大子矩阵和)
题目很简单,就是个最大子矩阵和的裸题,看来算法课本的分析后也差不多会做了。利用最大子段和的O(n)算法,对矩阵的行(或列)进行 i和j的枚举,对于第 i到j行,把同一列的元素进行压缩,得到一整行的一维数组后直接调用O(n)算法即可。我一开始还想着同一列的元素压缩不是也要耗费O(n)的时间吗,看了书上的代码后才知道原来数组b[]的每个元素都可以利用上一次的结果在O(1)时间内算出(当 i固定,j向下枚举时),当 i移动时,b[]就要清零进行重新计算了(在这里很奇怪动态分配的数组竟然不能直接用memset来清零,必须手动开个for循环来清零的,为了先跳过这些细枝末节只好开个全局数组了),代码如下:
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 const int INF= 0x3fffffff; 6 int a[108][108]; 7 8 int maxSum(int n, int c[]){ 9 int sum= -INF, b=0;10 for(int i=1; i<=n; ++i){11 if(b>=0) b+= c[i];12 else b= c[i];13 if(b>sum) sum=b;14 }15 return sum;16 }17 18 int b[108];19 int maxMatrix(int n, int a[][108]){20 int sum= -INF;21 // int *b= new int[n+1];22 // printf("%d\n",sizeof(b));23 for(int i=1; i<=n; ++i){24 memset(b,0,sizeof(b));25 // for(int k=1; k<=n; ++k) b[k]= 0;26 for(int j=i; j<=n; ++j){27 for(int k=1; k<=n; ++k) b[k]+= a[j][k];28 sum= max(sum, maxSum(n,b));29 }30 }31 return sum;32 }33 34 int main(){35 int n;36 while(~scanf("%d",&n)){37 for(int i=1; i<=n; ++i)38 for(int j=1; j<=n; ++j)39 scanf("%d",a[i]+j);40 printf("%d\n",maxMatrix(n,a));41 }42 }
hdu 1081(最大子矩阵和)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。