UC知道ACM的一道矩阵问题
来源：百度知道 编辑：UC知道 时间：2024/05/14 16:41:31
最大和问题 Max Sum
Time Limit:1000MS Memory Limit:32768K
Total Submit:223 Accepted:65
Description
给定一个2维的由正数组成的整数矩阵，找出其中具有最大和的子矩阵。一个矩阵的和就是矩阵中所有元素的和。本题中，具有最大和的子矩阵称为最大子矩阵。子矩阵是指位于整个矩阵中任何一个1×1或更大的连续的子矩阵。例如，在矩阵
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2
中其最大子矩阵在其左下角：
9 2
-4 1
-1 8
其和为15。
Input
输入由一个N*N的整数矩阵组成。输入的第一行是一个正整数N，表示该2维矩阵（方阵）的大小。接下来是N^2个整数，用空格（新开一行或若干空格）隔开。这N^2个整数以行为主顺序构成矩阵（如所有整数从左到右先构成第一行，接着余下所有整数再从左到右构成第二行，以此类推）。N最大可取100。矩阵元素的取值范围是[-127，127]。
Output
输出为最大子矩阵的和。
Sample Input
4
0 –2 –7 0 9 2 –6 2
-4 1 –4 1 –1
8 0 -2
Sample Output
15
Source
uva 108
我是个新手！请高手帮我一下！ 它的结果是什么样的！ 谢谢了！！！
Time Limit:1000MS Memory Limit:32768K
Total Submit:223 Accepted:65
Description
给定一个2维的由正数组成的整数矩阵，找出其中具有最大和的子矩阵。一个矩阵的和就是矩阵中所有元素的和。本题中，具有最大和的子矩阵称为最大子矩阵。子矩阵是指位于整个矩阵中任何一个1×1或更大的连续的子矩阵。例如，在矩阵
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2
中其最大子矩阵在其左下角：
9 2
-4 1
-1 8
其和为15。
Input
输入由一个N*N的整数矩阵组成。输入的第一行是一个正整数N，表示该2维矩阵（方阵）的大小。接下来是N^2个整数，用空格（新开一行或若干空格）隔开。这N^2个整数以行为主顺序构成矩阵（如所有整数从左到右先构成第一行，接着余下所有整数再从左到右构成第二行，以此类推）。N最大可取100。矩阵元素的取值范围是[-127，127]。
Output
输出为最大子矩阵的和。
Sample Input
4
0 –2 –7 0 9 2 –6 2
-4 1 –4 1 –1
8 0 -2
Sample Output
15
Source
uva 108
我是个新手！请高手帮我一下！ 它的结果是什么样的！ 谢谢了！！！
我 AC 的代码， 不过不是在UVA上AC的。
UVA的编译器跟国内ACM网站的编译器有些不同，教育网也上不去，所以就没有在UVA上提交。POJ上也有这个题目。
这个题目的算法就是动态规划。
#include<stdio.h>
#include<memory.h>
int n,a[100][100],b[100];
int dp1()
{
int sum=0,c=0,max=b[0];
for(int i=0;i<n;++i)
{
if(max<b[i])max=b[i];
if(c>0)c+=b[i];
else c=b[i];
if(c>sum)sum=c;
}
if(max<0) return max;
else return sum;
}
int dp()
{
int sum=-1000000000;
for(int i=0;i<n;++i)
{
memset(b,0,sizeof(b));
for(int j=i;j<n;++j)
{
for(int k=0;k<n;++k)
b[k]+=a[j][k];
int t=dp1();
if(sum<t)sum=t;
}
}
return sum;
}
int main()
{
while(scanf("%d",&n)!=-1)
{
for(int i=0;i<n;++i)
for(int j=0;j<n;++j)
scanf("%d",&a[i][j]);
printf("%d\n",dp(