练习题 - 最大加权矩形(动态规划)

前言

算法拾遗继续。

题目

给定一个正整数n( n<=100), 然后输入一个N*N矩阵。 求矩阵中最大加权矩形,即矩阵的每一个元素都有一权值,权值定义在整数集上。 从中找一矩形,矩形大小无限制,是其中包含的所有元素的和最大 。 矩阵的每个元素属于[-127,127]

例:

0 –2 –7  0             
9  2 –6  2                            
-4  1 –4  1                       
-1  8  0 –2

在左下角:

9  2
-4  1
-1  8

和为15

输入:

第一行:n,接下来是n行n列的矩阵。

输出:

最大矩形(子矩阵)的和。

样例: 输入:

4
0 –2 –7 0
 9 2 –6 2
-4 1 –4  1 
–1 8  0 –2

输出:

15

解答

用b[i][j]来存储前i行前j列的所有元素之和,b[i][j]=b[i][j-1]+b[i-1][j]-b[i-1][j-1]+a[i][j];

枚举b[x2][y2]-b[x1-1][y2]-b[x2][y1-1]+b[x1-1][y1-1]得到最大值。

#include <stdio.h>

FILE *in, *out;
int n, a[101][101], b[101][101]= {0}, max=-1270000;

int main() {
    in=fopen("B.in","r");
    out=fopen("B.out","w");
    fscanf(in,"%d",&n);

    int i,j;
    for(i=1; i<=n; i++)
        for(j=1; j<=n; j++)
            fscanf(in, "%d", &a[i][j]);

    /*
    for(i=1;i<=n;i++)
       {for(j=1;j<=n;j++)
          printf("%5d ",a[i][j]);
        printf("\n");
       }
    getchar();*/

    b[1][1]=a[1][1];

    for(i=1; i<=n; i++)
        for(j=1; j<=n; j++) {
            b[i][j]=b[i][j-1]+b[i-1][j]-b[i-1][j-1]+a[i][j];
            if(b[i][j]>max)
                max=b[i][j];
        }
    /*
     for(i=1;i<=n;i++)
       {for(j=1;j<=n;j++)
          printf("%5d ",b[i][j]);
        printf("\n");
       }
    getchar();*/

    int x1,y1,x2,y2,tem;
    for(x1=1; x1<=n; x1++)
        for(y1=1; y1<=n; y1++) {
            if(x1==1&&y1==1)
                continue;
            for(x2=x1; x2<=n; x2++)
                for(y2=y1; y2<=n; y2++) {
                    tem=b[x2][y2]-b[x1-1][y2]-b[x2][y1-1]+b[x1-1][y1-1];
                    if(tem>max)
                        max=tem;
                }
        }
    // printf("------------");getchar();
    fprintf(out,"%d",max);
    fclose(in);
    fclose(out);

    return 0;
}

参考


* cached version, generated at 2018-12-02 14:57:38 UTC.

Subscribe by RSS