首页 > 其他 > 详细

最大子矩阵(矩阵压缩)

时间:2015-10-16 15:13:23      阅读:232      评论:0      收藏:0      [点我收藏+]

最大子矩阵

Time Limit : 30000/10000ms (Java/Other)   Memory Limit : 32768/32768K (Java/Other)
Total Submission(s) : 1   Accepted Submission(s) : 1
Problem Description
给你一个m×n的整数矩阵,在上面找一个x×y的子矩阵,使子矩阵中所有元素的和最大。
 
Input
输入数据的第一行为一个正整数T,表示有T组测试数据。每一组测试数据的第一行为四个正整数m,n,x,y(0<m,n
 
Output
对于每组数据,输出一个整数,表示子矩阵的最大和。
 
Sample Input
1 4 5 2 2 3 361 649 676 588 992 762 156 993 169 662 34 638 89 543 525 165 254 809 280
 
Sample Output
2474
题解:矩阵压缩:
代码:
 1 #include<stdio.h>
 2 #include<string.h>
 3 #define MAX(x,y)(x>y?x:y)
 4 const int MAXN=1010;
 5 int m,n,x,y,ans;
 6 int map[MAXN][MAXN];
 7 void getline(int *a){
 8     for(int i=1;i+y<=n;i++){
 9         int temp=0;
10         for(int j=i,t=1;t<=y;j++,t++){
11             temp+=a[j];
12         }
13         ans=MAX(ans,temp);
14     }
15 }
16 int main(){
17     int T;
18     scanf("%d",&T);
19     while(T--){
20         scanf("%d%d%d%d",&m,&n,&x,&y);
21         ans=0;
22         for(int i=1;i<=m;i++){
23             for(int j=1;j<=n;j++)
24             scanf("%d",&map[i][j]);
25         }
26         for(int i=1;i+x<=m;i++){
27             for(int j=i+1,t=1;t<x;j++,t++){
28                 for(int k=1;k<=n;k++)
29                 map[i][k]+=map[j][k];
30             }
31             getline(map[i]);
32         }
33         printf("%d\n",ans);
34     }
35     return 0;
36 } 

 

最大子矩阵(矩阵压缩)

原文:http://www.cnblogs.com/handsomecui/p/4885073.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!