当前位置：首页 > news >正文

To the Max

news 来源：原创 2024/9/21 13:28:45

To the Max poj-1050

　　　　题目大意：给你一个n*n的矩阵，求最大子矩阵的和。每一个数不一定是正数。

　　　　注释：n<=100.

　　　　　　想法：以前听学长讲过bz的玉蟾宫，好像这题可以$n^3$。我在此介绍$n^3$的做法。这其实是一种扩展：首先，我们会O(n)的求一串数的最大连续字段和。我们想，如何才能处理出矩阵层面的最大子矩阵呢？我们想，我既然会求一串数的最大连续字段和，那么我们就可以将这个过程进行拓展，我们可以求出任意两行之间的最大子矩阵，这个子矩阵的上下两条边分别在这两行上。这样的话我们怎么处理，比如说我们枚举到了i行到j行，那么，我们对于每一列的元素，就可以将每一列的元素相加成一个，然后用O(n)的算法求出最大子矩阵，然后维护前缀和，before[i][j]表示for(int k=1;k<=i;k++) ans+=a[k][j]，即可。

　　　　最后，附上丑陋的代码... ...

 1 #include <iostream>
 2 #include <cstdio>
 3 using namespace std;
 4 int a[110][110];
 5 int before[110][110];
 6 int main()
 7 {
 8     int n;
 9     scanf("%d",&n);
10     for(int i=1;i<=n;i++)
11     {
12         for(int j=1;j<=n;j++)
13         {
14             scanf("%d",&a[i][j]);
15         }
16     }
17     for(int i=1;i<=n;i++)
18     {
19         for(int j=1;j<=n;j++)
20         {
21             before[i][j]=before[i-1][j]+a[i][j];
22         }
23     }
24     int maxmid=0xefefefef;
25     int maxbefore=0xefefefef;
26     int maxall=0xefefefef;
27     for(int i=1;i<=n;i++)
28     {
29         for(int j=i;j<=n;j++)
30         {
31             maxbefore=0;
32             maxmid=0xefefefef;
33             for(int k=1;k<=n;k++)
34             {
35                 if(maxbefore<0) maxbefore=before[j][k]-before[i-1][k];
36                 else maxbefore+=before[j][k]-before[i-1][k];
37                 maxmid=max(maxmid,maxbefore);
38             }
39             maxall=max(maxall,maxmid);
40         }
41     }
42     printf("%d\n",maxall);
43     return 0;
44 }