百练 OJ 2766 最大子矩阵

这篇博客是从旧博客 WordPress 迁移过来，内容可能存在转换异常。

//ID: 百练 OJ 2766 最大子矩阵 //题目地址： http://poj.grids.cn/problem/2766 //My Name: Tanky_Woo //My Website: C++奋斗乐园|C++学习|算法学习|ACM/ICPC学习 //Website Link: http://www.cpply.com/ //My BBS: C++奋斗乐园|C++论坛|算法论坛|ACM/ICPC论坛 //BBS Link：http://www.cppleyuan.com/ //My Blog：www.wutianqi.com //转载请写上本帖链接 www.cpply.com|www.cppleyuan.com|www.wutianqi.com //及名称"Tanky Woo与ACM一起走过的日子"和“C++奋斗乐园|C++论坛|算法论坛|ACM/ICPC论坛”

 //方法一
/*思想很经典，即利用求数组最长子段的函数。现在考虑如何利用这个函数，从第一行开始，到N行，遍历每种情况：
第i行到第j行上下元素相加，压缩成一个数组*/
#include 
using namespace std;

int N;
int aMatrix[101][101];
int aLine[101];
#define INF -10000000

int maxSubMatrix(int *line);

int main()
{
    //freopen("input_2766.txt", "r", stdin);
    int maxSum = INF;
    int i, j, k , h;
    scanf("%d", &N;);
    for(i = 0; i < N; i++)
        for(j = 0; j < N; j++)
            scanf("%d", &aMatrix;[i][j]);
    for(k = 0; k < N; k++)
    {
        for(h = k; h < N; h++)
        {
            for(j = 0; j < N; j++)
                aLine[j] += aMatrix[h][j];
            int sum = maxSubMatrix(aLine);
            if(sum > maxSum)
                maxSum = sum;
        }
        memset(aLine, 0, sizeof(aLine));


    }
    printf("%d\n", maxSum);
    return 0;
}



int maxSubMatrix(int *line)  //求数组的最长子段
{
    int i;
    int b = line[0], sum = line[0];
    for(i = 1; i < N; i++)
    {
        if(sum > 0)     //这个地方应该是判断b是否大于0，我先写成了sum，结果测试了几组数据是对的，但其实是错的！
            b += line[i];
        else
            b = line[i];

        if(b > sum)
            sum = b;
    }

    return sum;
}

 //方法二：
/*这题应该算用了DP吧。*/

#include
#include
int a[102][102];
int b[102][102];

int main(){
 //1.两个坐标点就确定了一个矩阵，然后枚举所有的矩阵(直接枚举会超时)
 //2.先计算（0,0）(i.j)确定的矩阵的值b[i][j]
 //3.枚举所有矩阵，利用b[i][j]分割计算 
 int n,ma=0;
 scanf("%d",&n;);
 for(int i=0;i<=n+1;i++){//设置边框
  a[0][i]=0;
  a[n+1][i]=0;
  a[i][0]=0;
  a[i][n+1]=0;
 }

 for(int i=1;i<=n;i++)//输入
  for(int j=1;j<=n;j++){
   scanf("%d",&a;[i][j]);
   if(a[i][j]>ma)ma=a[i][j];
  }


 for(int i=0;i<=n;i++)        //求b[i][j]
  for(int j=0;j<=n;j++)
   for(int p=0;p<=i;p++)
    for(int q=0;q<=j;q++)
     b[i][j]+=a[p][q];
 int sum=0;
 for(int i=1;i<=n;i++)    //枚举矩阵
  for(int j=1;j<=n;j++)
   for(int p=i;p<=n;p++)
    for(int q=j;q<=n;q++){
     sum=0;
     sum=b[p][q]-b[p][j-1]-b[i-1][q]+b[i-1][j-1];
     if(sum>ma)ma=sum;

    }
 printf("%d",ma);

}