poj 1050 最大子矩阵和

简介:

一、思路

最大子矩阵和的方法和最大字段和一样

先单独对每行求最大字段和(此时,子矩阵的行为1,就是最大字段和了)

然后,把第i行后的各行对应列的元素加到第i行的对应列元素,每加一行,就求一次最大字段和,这样就把子矩阵的多行压缩为一行了,一行了就是最大字段和了

也可以这样理解:

a11 a12 a13
a21 a22 a23
a31 a32 a33

如图,先求第一行最大子段和,再求第一行跟第二行合起来的最大子段和,如a21+a11, a22+a12, a23+a13 的最大子段和,再求第一到第三合起来的最大子段和,如a11+a21+a31, a12+a22+a32, a13+a23+a33的最大子段和…..以此类推,直到求出整个矩阵的合起来的最大子段和,求出他们之中最大的那个和就是解.

二、AC code

#include <stdio.h>
#include <stdlib.h>

int m[101][101];

int main()
{
    int n,max,i,j,k,tmp;

    while(scanf("%d",&n) != EOF)
    {
        max=-10000;
        /*
        输入时,顺便求出各行的最大字段和的最大值
        */
        for(i=0;i<n;++i)
        {
            tmp=0;
            for(j=0;j<n;++j)
            {
                scanf("%d",&m[i][j]);
                if(tmp>0)tmp+=m[i][j];
                else tmp=m[i][j];

                if(tmp>max)max=tmp;
            }
        }

        for(i=0;i<n-1;++i)
        {
            for(j=i+1;j<n;++j)
            {
                tmp=0;
                for(k=0;k<n;++k)
                {
                    //相当于把子矩阵多行压缩为一行了
                    m[i][k]+=m[j][k];
                    if(tmp>0)tmp+=m[i][k];
                    else tmp=m[i][k];

                    if(tmp>max)max=tmp;
                }
            }

        }
        printf("%d\n",max);
    }

    return 0;   
}
相关文章
|
机器学习/深度学习
A-POJ-1321 棋盘问题
Description 在一个给定形状的棋盘(形状可能是不规则的)上面摆放棋子,棋子没有区别。
940 0
|
测试技术
POJ 1001
此题用最朴素的思路实现即可,需模拟加法器,乘法器,最烦人的地方是特殊情形,如末位是小数点(12.^2=144,取小数点),整数末位是0(100^2=10000),0次幂,测试用例可能超出题目中说的范围,可能包含0次幂(100.0^0=0, 0.10^1=0.1)。
755 0
poj 3620
题意:给出一个矩阵,其中有些格子干燥、有些潮湿。       如果一个潮湿的格子的相邻的四个方向有格子也是潮湿的,那么它们就可以构成更大       的湖泊,求最大的湖泊。       也就是求出最大的连在一块儿的潮湿的格子的数目。
577 0
poj 1455
Description n participants of > sit around the table. Each minute one pair of neighbors can change their places.
622 0
poj 3664
http://poj.org/problem?id=3664 进行两轮选举,第一轮选前n进入第二轮,第二轮选最高   #include #include using namespace std; struct vote { int a,b; int c; ...
738 0
POJ-1003-hangover
Description How far can you make a stack of cards overhang a table? If you have one card, you can create a maximum overhang of half a card length.
769 0
|
人工智能 vr&ar